Demonstration of covariance matrix and basis function implementation of Gaussian process model in Stan.

The basics of the covariance matrix approach is based on the Chapter 10 of Stan User’s Guide, Version 2.26 by Stan Development Team (2021). https://mc-stan.org/docs/stan-users-guide/

The basics of the Hilbert space basis function approximation is based on Riutort-Mayol, Bürkner, Andersen, Solin, and Vehtari (2020). Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programming. https://arxiv.org/abs/2004.11408

Motorcycle

Data are measurements of head acceleration in a simulated motorcycle accident, used to test crash helmets.

Data are modelled first with normal distribution having Gaussian process prior on mean: \[ y \sim \mbox{normal}(f(x), \sigma)\\ f \sim GP(0, K_1)\\ \sigma \sim \mbox{normal}^{+}(0, 1), \] and then with normal distribution having Gaussian process prior on mean and log standard deviation: \[ y \sim \mbox{normal}(f(x), \exp(g(x))\\ f \sim GP(0, K_1)\\ g \sim GP(0, K_2). \]

Load packages

library(cmdstanr) 
library(posterior)
library(tidybayes)
options(pillar.neg = FALSE, pillar.subtle=FALSE, pillar.sigfig=2)
library(tidyr) 
library(dplyr) 
library(ggplot2)
library(bayesplot)
theme_set(bayesplot::theme_default(base_family = "sans", base_size=16))
set1 <- RColorBrewer::brewer.pal(7, "Set1")
SEED <- 48927 # set random seed for reproducibility

Motorcycle accident acceleration data

Load data

data(mcycle, package="MASS")
head(mcycle)
  times accel
1   2.4   0.0
2   2.6  -1.3
3   3.2  -2.7
4   3.6   0.0
5   4.0  -2.7
6   6.2  -2.7

Plot data

mcycle %>%
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")

GP model with homoskedastic residual

We start with a simpler homoskedastic residual Gaussian process model \[ y \sim \mbox{normal}(f(x), \sigma)\\ f \sim GP(0, K_1)\\ \sigma \sim normal^{+}(0, 1), \] that has analytic marginal likelihood for the covariance function and residual scale parameters.

Model code

file_gpcovf <- "gpcovf.stan"
writeLines(readLines(file_gpcovf))
functions {
  vector gp_pred_rng(real[] x2,
                     vector y1,
                     real[] x1,
                     real sigma_f,
                     real lengthscale_f,
                     real sigma,
                     real jitter) {
    int N1 = rows(y1);
    int N2 = size(x2);
    vector[N2] f2;
    {
      matrix[N1, N1] L_K;
      vector[N1] K_div_y1;
      matrix[N1, N2] k_x1_x2;
      matrix[N1, N2] v_pred;
      vector[N2] f2_mu;
      matrix[N2, N2] cov_f2;
      matrix[N1, N1] K;
      K = gp_exp_quad_cov(x1, sigma_f, lengthscale_f);
      for (n in 1:N1)
        K[n, n] = K[n,n] + square(sigma);
      L_K = cholesky_decompose(K);
      K_div_y1 = mdivide_left_tri_low(L_K, y1);
      K_div_y1 = mdivide_right_tri_low(K_div_y1', L_K)';
      k_x1_x2 = gp_exp_quad_cov(x1, x2, sigma_f, lengthscale_f);
      f2_mu = (k_x1_x2' * K_div_y1);
      v_pred = mdivide_left_tri_low(L_K, k_x1_x2);
      cov_f2 = gp_exp_quad_cov(x2, sigma_f, lengthscale_f) - v_pred' * v_pred;

      f2 = multi_normal_rng(f2_mu, add_diag(cov_f2, rep_vector(jitter, N2)));
    }
    return f2;
  }
}
data {
  int<lower=1> N;      // number of observations
  vector[N] x;         // univariate covariate
  vector[N] y;         // target variable
  int<lower=1> N2;     // number of test points
  vector[N2] x2;       // univariate test points
}
transformed data {
  // Normalize data
  real xmean = mean(x);
  real ymean = mean(y);
  real xsd = sd(x);
  real ysd = sd(y);
  real xn[N] = to_array_1d((x - xmean)/xsd);
  real x2n[N2] = to_array_1d((x2 - xmean)/xsd);
  vector[N] yn = (y - ymean)/ysd;
  real sigma_intercept = 0.1;
  vector[N] zeros = rep_vector(0, N);
}
parameters {
  real<lower=0> lengthscale_f; // lengthscale of f
  real<lower=0> sigma_f;       // scale of f
  real<lower=0> sigman;         // noise sigma
}
model {
  // covariances and Cholesky decompositions
  matrix[N, N] K_f = gp_exp_quad_cov(xn, sigma_f, lengthscale_f)+
                     sigma_intercept;
  matrix[N, N] L_f = cholesky_decompose(add_diag(K_f, sigman));
  // priors
  lengthscale_f ~ normal(0, 1);
  sigma_f ~ normal(0, 1);
  sigman ~ normal(0, 1);
  // model
  yn ~ multi_normal_cholesky(zeros, L_f);
}
generated quantities {
  // function scaled back to the original scale
  vector[N2] f = gp_pred_rng(x2n, yn, xn, sigma_f, lengthscale_f, sigman, 1e-9)*ysd + ymean;
  real sigma = sigman*ysd;
}

Compile Stan model

model_gpcovf <- cmdstan_model(stan_file = file_gpcovf)

Data to be passed to Stan

standata_gpcovf <- list(x=mcycle$times,
                        x2=mcycle$times,
                        y=mcycle$accel,
                        N=length(mcycle$times),
                        N2=length(mcycle$times))

Optimize and find MAP estimate

opt_gpcovf <- model_gpcovf$optimize(data=standata_gpcovf,
                                    init=0.1, algorithm='bfgs')

Check whether parameters have reasonable values

odraws_gpcovf <- as_draws_rvars(opt_gpcovf$draws())
subset(odraws_gpcovf, variable=c('sigma_','lengthscale_','sigma'), regex=TRUE)
# A draws_rvars: 1 iterations, 1 chains, and 4 variables
$sigma_f: rvar<1>[1] mean ± sd:
[1] 0.89 ± NA 

$lengthscale_f: rvar<1>[1] mean ± sd:
[1] 0.39 ± NA 

$sigman: rvar<1>[1] mean ± sd:
[1] 0.22 ± NA 

$sigma: rvar<1>[1] mean ± sd:
[1] 11 ± NA 

Compare the model to the data

mcycle %>%
  mutate(Ef=mean(odraws_gpcovf$f),
         sigma=mean(odraws_gpcovf$sigma)) %>%  
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The model fit given optimized parameters, looks reasonable considering the use of homoskedastic residual model.

Sample using dynamic HMC

fit_gpcovf <- model_gpcovf$sample(data=standata_gpcovf,
                                  iter_warmup=500, iter_sampling=500,
                                  chains=4, parallel_chains=4, refresh=100)

Check whether parameters have reasonable values

draws_gpcovf <- as_draws_rvars(fit_gpcovf$draws())
summarise_draws(subset(draws_gpcovf,
                       variable=c('sigma_','lengthscale_','sigma'),
                       regex=TRUE))
# A tibble: 4 × 10
  variable       mean median    sd   mad    q5   q95  rhat ess_bulk ess_tail
  <chr>         <dbl>  <dbl> <dbl> <dbl> <dbl> <dbl> <dbl>    <dbl>    <dbl>
1 sigma_f        1.0    0.97 0.29  0.26   0.64  1.6    1.0    1336.    1205.
2 lengthscale_f  0.40   0.40 0.061 0.063  0.30  0.50   1.0    1197.    1165.
3 sigman         0.23   0.22 0.030 0.030  0.18  0.28   1.0    1138.     981.
4 sigma         11.    11.   1.5   1.4    8.8  14.     1.0    1138.     981.

Compare the model to the data

mcycle %>%
  mutate(Ef=mean(draws_gpcovf$f),
         sigma=mean(draws_gpcovf$sigma)) %>%  
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The model fit given integrated parameters looks similar to the optimized one.

Compare the posterior draws to the optimized parameters

odraws_gpcovf <- as_draws_df(opt_gpcovf$draws())
draws_gpcovf %>%
  as_draws_df() %>%
  ggplot(aes(x=lengthscale_f,y=sigma_f))+
  geom_point(color=set1[2])+
  geom_point(data=odraws_gpcovf,color=set1[1],size=4)+
  annotate("text",x=median(draws_gpcovf$lengthscale_f),
           y=max(draws_gpcovf$sigma_f)+0.1,
           label='Posterior draws',hjust=0.5,color=set1[2],size=6)+
  annotate("text",x=odraws_gpcovf$lengthscale_f+0.01,
           y=odraws_gpcovf$sigma_f,
           label='Optimized',hjust=0,color=set1[1],size=6)

The optimization result is in the middle of the posterior and quite well representative of the low dimensional posterior (in higher dimensions the mean or mode of the posterior is not likely to be representative).

Compare optimized and posterior predictive distributions

odraws_gpcovf <- as_draws_rvars(opt_gpcovf$draws())
mcycle %>%
  mutate(Ef=mean(draws_gpcovf$f),
         sigma=mean(draws_gpcovf$sigma),
         Efo=mean(odraws_gpcovf$f),
         sigmao=mean(odraws_gpcovf$sigma)) %>%
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Efo), color=set1[2])+
  geom_line(aes(y=Efo-2*sigmao), color=set1[2],linetype="dashed")+
  geom_line(aes(y=Efo+2*sigmao), color=set1[2],linetype="dashed")

The model predictions are very similar, and in general GP covariance function and observation model parameters can be quite safely optimized if there are only a few of them and thus marginal posterior is low dimensional and the number of observations is relatively high.

10% of data

To demonstrate that the optimization is not always safe, we use only 10% of the data for model fitting.

Data to be passed to Stan

mcycle_10p <- mcycle[seq(1,133,by=10),]
standata_10p <- list(x=mcycle_10p$times,
                     x2=mcycle$times,
                     y=mcycle_10p$accel,
                     N=length(mcycle_10p$times),
                     N2=length(mcycle$times))

Optimize and find MAP estimate

opt_10p <- model_gpcovf$optimize(data=standata_10p, init=0.1,
                                 algorithm='lbfgs')

Check whether parameters have reasonable values

odraws_10p <- as_draws_rvars(opt_10p$draws())
subset(odraws_10p, variable=c('sigma_','lengthscale_','sigma'), regex=TRUE)
# A draws_rvars: 1 iterations, 1 chains, and 4 variables
$sigma_f: rvar<1>[1] mean ± sd:
[1] 0.91 ± NA 

$lengthscale_f: rvar<1>[1] mean ± sd:
[1] 0.25 ± NA 

$sigman: rvar<1>[1] mean ± sd:
[1] 0.033 ± NA 

$sigma: rvar<1>[1] mean ± sd:
[1] 1.5 ± NA 

Compare the model to the data

mcycle_10p %>%
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(data=mcycle,aes(x=times,y=mean(odraws_10p$f)), color=set1[1])+
  geom_line(data=mcycle,aes(x=times,y=mean(odraws_10p$f-2*odraws_10p$sigma)), color=set1[1],
            linetype="dashed")+
  geom_line(data=mcycle,aes(x=times,y=mean(odraws_10p$f+2*odraws_10p$sigma)), color=set1[1],
            linetype="dashed")

The model fit is clearly over-fitted and over-confident.

Sample using dynamic HMC

fit_10p <- model_gpcovf$sample(data=standata_10p,
                               iter_warmup=1000, iter_sampling=1000,
                               adapt_delta=0.95,
                               chains=4, parallel_chains=4, refresh=100)

Check whether parameters have reasonable values

draws_10p <- as_draws_rvars(fit_10p$draws())
summarise_draws(subset(draws_10p, variable=c('sigma_','lengthscale_','sigma'),
                       regex=TRUE))
# A tibble: 4 × 10
  variable       mean median    sd   mad    q5   q95  rhat ess_bulk ess_tail
  <chr>         <dbl>  <dbl> <dbl> <dbl> <dbl> <dbl> <dbl>    <dbl>    <dbl>
1 sigma_f        0.90   0.89  0.38  0.33 0.24    1.6   1.0    1155.     602.
2 lengthscale_f  0.40   0.31  0.33  0.13 0.14    1.1   1.0     925.    1016.
3 sigman         0.39   0.26  0.37  0.27 0.036   1.2   1.0     697.    1238.
4 sigma         17.    12.   16.   12.   1.6    52.    1.0     697.    1238.

Compare the model to the data

mcycle_10p %>%
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(data=mcycle,aes(x=times,y=mean(draws_10p$f)), color=set1[1])+
  geom_line(data=mcycle,aes(x=times,y=mean(draws_10p$f-2*draws_10p$sigma)), color=set1[1],
            linetype="dashed")+
  geom_line(data=mcycle,aes(x=times,y=mean(draws_10p$f+2*draws_10p$sigma)), color=set1[1],
            linetype="dashed")

The posterior predictive distribution is much more conservative and shows the uncertainty due to having only a small number of observations.

Compare the posterior draws to the optimized parameters

odraws_10p <- as_draws_df(opt_10p$draws())
draws_10p %>%
  thin_draws(thin=5) %>%
  as_draws_df() %>%
  ggplot(aes(x=sigma,y=sigma_f))+
  geom_point(color=set1[2])+
  geom_point(data=odraws_10p,color=set1[1],size=4)+
  annotate("text",x=median(draws_10p$sigma),
           y=max(draws_10p$sigma_f)+0.1,
           label='Posterior draws',hjust=0.5,color=set1[2],size=6)+
  annotate("text",x=odraws_10p$sigma+0.01,
           y=odraws_10p$sigma_f,
           label='Optimized',hjust=0,color=set1[1],size=6)

The optimization result is in the edge of the posterior close to zero residual scale. While there are posterior draws close to zero, integrating over the wide posterior takes into account the uncertainty and the predictions thus are more uncertain, too.

Compare optimized and posterior predictive distributions

odraws_10p <- as_draws_rvars(opt_10p$draws())
mcycle %>%
  mutate(Ef=mean(draws_10p$f),
         sigma=mean(draws_10p$sigma),
         Efo=mean(odraws_10p$f),
         sigmao=mean(odraws_10p$sigma)) %>%
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Efo), color=set1[2])+
  geom_line(aes(y=Efo-2*sigmao), color=set1[2],linetype="dashed")+
  geom_line(aes(y=Efo+2*sigmao), color=set1[2],linetype="dashed")

The figure shows the model prediction given 10% of data, but also the full data as test data. The optimized model is over-fitted and overconfident. Even if the homoskedastic residual is wrong here, the posterior predictive interval covers most of the observation (and in case of good calibration should not cover them all).

GP with covariance matrices

We next make a model with heteroskedastic residual model using Gaussian process prior also for the logarithm of the residual scale: \[ y \sim \mbox{normal}(f(x), \exp(g(x))\\ f \sim GP(0, K_1)\\ g \sim GP(0, K_2). \]

Now there is no analytical solution as GP prior through the exponential function is not a conjugate prior. In this case we present the latent values of f and g explicitly and sample from the joint posterior of the covariance function parameters, and the latent values. It would be possible also to use Laplace, variational inference, or expectation propagation to integrate over the latent values, but that is another story.

Model code

file_gpcovfg <- "gpcovfg.stan"
writeLines(readLines(file_gpcovfg))
data {
  int<lower=1> N;      // number of observations
  vector[N] x;         // univariate covariate
  vector[N] y;         // target variable
}
transformed data {
  // Normalize data
  real xmean = mean(x);
  real ymean = mean(y);
  real xsd = sd(x);
  real ysd = sd(y);
  real xn[N] = to_array_1d((x - xmean)/xsd);
  vector[N] yn = (y - ymean)/ysd;
  real sigma_intercept = 0.1;
  vector[N] jitter = rep_vector(1e-9, N);
}
parameters {
  real<lower=0> lengthscale_f; // lengthscale of f
  real<lower=0> sigma_f;       // scale of f
  real<lower=0> lengthscale_g; // lengthscale of g
  real<lower=0> sigma_g;       // scale of g
  vector[N] z_f;
  vector[N] z_g;
}
model {
  // covariances and Cholesky decompositions
  matrix[N, N] K_f = gp_exp_quad_cov(xn, sigma_f, lengthscale_f)+
                     sigma_intercept;
  matrix[N, N] L_f = cholesky_decompose(add_diag(K_f, jitter));
  matrix[N, N] K_g = gp_exp_quad_cov(xn, sigma_g, lengthscale_g)+
                     sigma_intercept;
  matrix[N, N] L_g = cholesky_decompose(add_diag(K_g, jitter));
  // priors
  z_f ~ std_normal();
  z_g ~ std_normal();
  lengthscale_f ~ lognormal(log(.3), .2);
  lengthscale_g ~ lognormal(log(.5), .2);
  sigma_f ~ normal(0, .5);
  sigma_g ~ normal(0, .5);
  // model
  yn ~ normal(L_f * z_f, exp(L_g * z_g));
}
generated quantities {
  vector[N] f;
  vector[N] sigma;
  {
    // covariances and Cholesky decompositions
    matrix[N, N] K_f = gp_exp_quad_cov(xn, sigma_f, lengthscale_f)+
                       sigma_intercept;
    matrix[N, N] L_f = cholesky_decompose(add_diag(K_f, jitter));
    matrix[N, N] K_g = gp_exp_quad_cov(xn, sigma_g, lengthscale_g)+
                       sigma_intercept;
    matrix[N, N] L_g = cholesky_decompose(add_diag(K_g, jitter));
    // function scaled back to the original scale
    f = (L_f * z_f)*ysd + ymean;
    sigma = exp(L_g * z_g)*ysd;
  }
}

Compile Stan model

model_gpcovfg <- cmdstan_model(stan_file = file_gpcovfg)

Data to be passed to Stan

standata_gpcovfg <- list(x=mcycle$times,
                         y=mcycle$accel,
                         N=length(mcycle$times))

Optimize and find MAP estimate

opt_gpcovfg <- model_gpcovfg$optimize(data=standata_gpcovfg,
                                      init=0.1, algorithm='bfgs')

Check whether parameters have reasonable values

odraws_gpcovfg <- as_draws_rvars(opt_gpcovfg$draws())
subset(odraws_gpcovfg, variable=c('sigma_','lengthscale_'), regex=TRUE)
# A draws_rvars: 1 iterations, 1 chains, and 4 variables
$sigma_f: rvar<1>[1] mean ± sd:
[1] 1.5 ± NA 

$sigma_g: rvar<1>[1] mean ± sd:
[1] 3.6 ± NA 

$lengthscale_f: rvar<1>[1] mean ± sd:
[1] 0.11 ± NA 

$lengthscale_g: rvar<1>[1] mean ± sd:
[1] 0.19 ± NA 

Compare the model to the data

mcycle %>%
  mutate(Ef = mean(odraws_gpcovfg$f),
         sigma = mean(odraws_gpcovfg$sigma)) %>%
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The optimization overfits, as we are now optimizing the joint posterior of 2 covariance function parameters and 2 x 133 latent values.

Sample using dynamic HMC

fit_gpcovfg <- model_gpcovfg$sample(data=standata_gpcovfg,
                                    iter_warmup=100, iter_sampling=100,
                                    chains=4, parallel_chains=4, refresh=10)

Check whether parameters have reasonable values

draws_gpcovfg <- as_draws_rvars(fit_gpcovfg$draws())
summarise_draws(subset(draws_gpcovfg, variable=c('sigma_','lengthscale_'),
                       regex=TRUE))
# A tibble: 4 × 10
  variable       mean median    sd   mad    q5   q95  rhat ess_bulk ess_tail
  <chr>         <dbl>  <dbl> <dbl> <dbl> <dbl> <dbl> <dbl>    <dbl>    <dbl>
1 sigma_f        0.77   0.75 0.16  0.15   0.55  1.1    1.0     327.       NA
2 sigma_g        1.2    1.2  0.22  0.23   0.85  1.6    1.0     653.       NA
3 lengthscale_f  0.32   0.31 0.036 0.036  0.27  0.38   1.0     166.       NA
4 lengthscale_g  0.50   0.50 0.073 0.071  0.38  0.62   1.0     314.       NA

Compare the model to the data

mcycle %>%
  mutate(Ef = mean(draws_gpcovfg$f),
         sigma = mean(draws_gpcovfg$sigma)) %>%
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The MCMC integration works well and the model fit looks good.

Plot posterior draws and posterior mean of the mean function

draws_gpcovfg %>%
  thin_draws(thin=5) %>%
  spread_rvars(f[i]) %>%
  unnest_rvars() %>%
  mutate(time=mcycle$times[i]) %>%
  ggplot(aes(x=time, y=f, group = .draw)) +
  geom_line(color=set1[2], alpha = 0.1) +
  geom_point(data=mcycle, mapping=aes(x=times,y=accel), inherit.aes=FALSE) +
  geom_line(data=mcycle, mapping=aes(x=times,y=mean(draws_gpcovfg$f)),
            inherit.aes=FALSE, color=set1[1], size=1)+
  labs(x="Time (ms)", y="Acceleration (g)")

We can also plot the posterior draws of the latent functions, which is a good reminder that individual draws are more wiggly than the average of the draws, and thus show better also the uncertainty, for example, in the edge of the data.

Compare the posterior draws to the optimized parameters

odraws_gpcovfg <- as_draws_df(opt_gpcovfg$draws())
draws_gpcovfg %>%
  thin_draws(thin=5) %>%
  as_draws_df() %>%
  ggplot(aes(x=lengthscale_f,y=sigma_f))+
  geom_point(color=set1[2])+
  geom_point(data=odraws_gpcovfg,color=set1[1],size=4)+
  annotate("text",x=median(draws_gpcovfg$lengthscale_f),
           y=max(draws_gpcovfg$sigma_f)+0.1,
           label='Posterior draws',hjust=0.5,color=set1[2],size=6)+
  annotate("text",x=odraws_gpcovfg$lengthscale_f+0.01,
           y=odraws_gpcovfg$sigma_f,
           label='Optimized',hjust=0,color=set1[1],size=6)

Optimization result is far from being representative of the posterior.

GP model with Hilbert basis functions

The covariance matrix approach requires computation of Cholesky of the covariance matrix which has time cost O(n^3) and this is needs to be done every time the parameters change, which in case of MCMC can be quite many times and thus the computation time can be significant when n grows. One way to speed up the computation in low dimensional covariate case is to use basis function approximation which changes the GP to a linear model. Here we use Hilbert space basis functions.

Code for illustrating the basis functions Model code

filebf0 <- "gpbf0.stan"
writeLines(readLines(filebf0))
functions {
#include gpbasisfun_functions.stan
}
data {
  int<lower=1> N;      // number of observations
  vector[N] x;         // univariate covariate
        
  real<lower=0> c_f;   // factor c to determine the boundary value L
  int<lower=1> M_f;    // number of basis functions
  real<lower=0> lengthscale_f; // lengthscale of f
  real<lower=0> sigma_f;       // scale of f
}
transformed data {
  // Normalize data
  real xmean = mean(x);
  real xsd = sd(x);
  vector[N] xn = (x - xmean)/xsd;
  // Basis functions for f
  real L_f = c_f*max(xn);
}
generated quantities {
  // Basis functions for f
  matrix[N,M_f] PHI_f = PHI(N, M_f, L_f, xn);
  // spectral densities
  vector[M_f] diagSPD_f = diagSPD_EQ(sigma_f, lengthscale_f, L_f, M_f);
}

The model code includes Hilbert space basis function helpers

writeLines(readLines("gpbasisfun_functions.stan"))
vector diagSPD_EQ(real alpha, real rho, real L, int M) {
  return sqrt((alpha^2) * sqrt(2*pi()) * rho * exp(-0.5*(rho*pi()/2/L)^2 * linspaced_vector(M, 1, M)^2));
}
vector diagSPD_Matern(real alpha, real rho, real L, int M) {
   return sqrt(4*alpha^2 * (sqrt(3)/rho)^3 * inv((sqrt(3)/rho)^2 + ((pi()/2/L) * linspaced_vector(M, 1, M))^2)^2);
  }
vector diagSPD_periodic(real alpha, real rho, int M) {
  real a = 1/rho^2;
  int one_to_M[M];
  for (m in 1:M) one_to_M[m] = m;
  vector[M] q = sqrt(alpha^2 * 2 / exp(a) * to_vector(modified_bessel_first_kind(one_to_M, a)));
  return append_row(q,q);
}
matrix PHI(int N, int M, real L, vector x) {
  matrix[N,M] PHIp = sin(diag_post_multiply(rep_matrix(pi()/(2*L) * (x+L), M), linspaced_vector(M, 1, M)))/sqrt(L);
  for (m in 1:M)
    PHIp[,m] = PHIp[,m] - mean(PHIp[,m]);
  return PHIp;
}
matrix PHI_periodic(int N, int M, real w0, vector x) {
  matrix[N,M] mw0x = diag_post_multiply(rep_matrix(w0*x, M), linspaced_vector(M, 1, M));
  matrix[N,M] PHIp = append_col(cos(mw0x), sin(mw0x));
  for (m in 1:M)
    PHIp[,m] = PHIp[,m] - mean(PHIp[,m]);
  return PHIp;
}

Compile basis function generation code

modelbf0 <- cmdstan_model(stan_file = filebf0, include_paths = ".")

Data to be passed to Stan

standatabf0 <- list(x=seq(0,1,length.out=100),
                    N=100,
                    c_f=1.5, # factor c of basis functions for GP for f1
                    M_f=40,  # number of basis functions for GP for f1
                    sigma_f=1,
                    lengthscale_f=1) 

Generate basis functions

fixbf0 <- modelbf0$sample(data=standatabf0, fixed_param=TRUE,
                          iter=1, iter_sampling=1)
Running MCMC with 1 chain...

Chain 1 Iteration: 1 / 1 [100%]  (Sampling) 
Chain 1 finished in 0.0 seconds.

There is certainly easier way to do this, but this is what I came up quickly

q<-subset(fixbf0$draws(), variable="PHI_f") %>%
  as_draws_matrix() %>%
  as.numeric()%>%
  matrix(nrow=100,ncol=40)%>%
  as.data.frame()
id <- rownames(q)
q <- cbind(x=as.numeric(id), q)
q <- q %>%
  pivot_longer(!x,
               names_to="ind",
               names_transform = list(ind = readr::parse_number),
               values_to="f")%>%
  mutate(x=x/100)

Plot 10 first basis functions

q %>%
  filter(ind<=10) %>%
  ggplot(aes(x=x, y=f, group=ind)) +
  geom_line() +
  facet_grid(rows=vars(ind))

And now the actual model using GP basis functions for f and g

Model code

file_gpbffg <- "gpbffg.stan"
writeLines(readLines(file_gpbffg))
functions {
#include gpbasisfun_functions.stan
}
data {
  int<lower=1> N;      // number of observations
  vector[N] x;         // univariate covariate
  vector[N] y;         // target variable
        
  real<lower=0> c_f;   // factor c to determine the boundary value L
  int<lower=1> M_f;    // number of basis functions
  real<lower=0> c_g;   // factor c to determine the boundary value L
  int<lower=1> M_g;    // number of basis functions
}
transformed data {
  // Normalize data
  real xmean = mean(x);
  real ymean = mean(y);
  real xsd = sd(x);
  real ysd = sd(y);
  vector[N] xn = (x - xmean)/xsd;
  vector[N] yn = (y - ymean)/ysd;
  // Basis functions for f
  real L_f = c_f*max(xn);
  matrix[N,M_f] PHI_f = PHI(N, M_f, L_f, xn);
  // Basis functions for g
  real L_g= c_g*max(xn);
  matrix[N,M_g] PHI_g = PHI(N, M_g, L_g, xn);
}
parameters {
  real intercept_f;
  real intercept_g;
  vector[M_f] beta_f;          // the basis functions coefficients
  vector[M_g] beta_g;          // the basis functions coefficients
  real<lower=0> lengthscale_f; // lengthscale of f
  real<lower=0> sigma_f;       // scale of f
  real<lower=0> lengthscale_g; // lengthscale of g
  real<lower=0> sigma_g;       // scale of g
}
model {
  // spectral densities for f and g
  vector[M_f] diagSPD_f = diagSPD_EQ(sigma_f, lengthscale_f, L_f, M_f);
  vector[M_g] diagSPD_g = diagSPD_EQ(sigma_g, lengthscale_g, L_g, M_g);
  // priors
  intercept_f ~ normal(0, 1);
  intercept_g ~ normal(0, 1);
  beta_f ~ normal(0, 1);
  beta_g ~ normal(0, 1);
  lengthscale_f ~ normal(0, 1);
  lengthscale_g ~ normal(0, 1);
  sigma_f ~ normal(0, .5);
  sigma_g ~ normal(0, .5);
  // model
  yn ~ normal(intercept_f + PHI_f * (diagSPD_f .* beta_f),
          exp(intercept_g + PHI_g * (diagSPD_g .* beta_g)));
}
generated quantities {
  vector[N] f;
  vector[N] sigma;
  {
    // spectral densities
    vector[M_f] diagSPD_f = diagSPD_EQ(sigma_f, lengthscale_f, L_f, M_f);
    vector[M_g] diagSPD_g = diagSPD_EQ(sigma_g, lengthscale_g, L_g, M_g);
    // function scaled back to the original scale
    f = (intercept_f + PHI_f * (diagSPD_f .* beta_f))*ysd + ymean;
    sigma = exp(intercept_g + PHI_g * (diagSPD_g .* beta_g))*ysd;
  }
}

Compile Stan model

model_gpbffg <- cmdstan_model(stan_file = file_gpbffg, include_paths = ".")

Data to be passed to Stan

standata_gpbffg <- list(x=mcycle$times,
                        y=mcycle$accel,
                        N=length(mcycle$times),
                        c_f=1.5, # factor c of basis functions for GP for f1
                        M_f=40,  # number of basis functions for GP for f1
                        c_g=1.5, # factor c of basis functions for GP for g3
                        M_g=40)  # number of basis functions for GP for g3

Optimize and find MAP estimate

opt_gpbffg <- model_gpbffg$optimize(data=standata_gpbffg,
                                    init=0.1, algorithm='bfgs')

Check whether parameters have reasonable values

odraws_gpbffg <- as_draws_rvars(opt_gpbffg$draws())
subset(odraws_gpbffg, variable=c('intercept','sigma_','lengthscale_'),
       regex=TRUE)
# A draws_rvars: 1 iterations, 1 chains, and 6 variables
$intercept_f: rvar<1>[1] mean ± sd:
[1] -0.0057 ± NA 

$intercept_g: rvar<1>[1] mean ± sd:
[1] -1.8 ± NA 

$sigma_f: rvar<1>[1] mean ± sd:
[1] 1.4 ± NA 

$sigma_g: rvar<1>[1] mean ± sd:
[1] 3.5 ± NA 

$lengthscale_f: rvar<1>[1] mean ± sd:
[1] 0.14 ± NA 

$lengthscale_g: rvar<1>[1] mean ± sd:
[1] 0.093 ± NA 

Compare the model to the data

mcycle %>%
  mutate(Ef=mean(odraws_gpbffg$f),
         sigma=mean(odraws_gpbffg$sigma)) %>%  
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The optimization overfits, as we are now optimizing the joint posterior of 2 covariance function parameters and 2 x 40 basis function co-efficients.

Sample using dynamic HMC

fit_gpbffg <- model_gpbffg$sample(data=standata_gpbffg,
                                  iter_warmup=500, iter_sampling=500, refresh=100,
                                  chains=4, parallel_chains=4, adapt_delta=0.9)

Check whether parameters have reasonable values

draws_gpbffg <- as_draws_rvars(fit_gpbffg$draws())
summarise_draws(subset(draws_gpbffg,
                       variable=c('intercept','sigma_','lengthscale_'),
                       regex=TRUE))
# A tibble: 6 × 10
  variable         mean  median    sd   mad     q5    q95  rhat ess_bulk ess_tail
  <chr>           <dbl>   <dbl> <dbl> <dbl>  <dbl>  <dbl> <dbl>    <dbl>    <dbl>
1 intercept_f    0.0090  0.0083 0.041 0.041 -0.061  0.076   1.0    2086.    1318.
2 intercept_g   -1.2    -1.2    0.069 0.067 -1.3   -1.1     1.0    1287.    1526.
3 sigma_f        0.83    0.80   0.18  0.16   0.58   1.2     1.0     903.     762.
4 sigma_g        1.0     0.98   0.20  0.19   0.72   1.4     1.0    1122.    1412.
5 lengthscale_f  0.34    0.34   0.050 0.052  0.26   0.43    1.0     717.    1011.
6 lengthscale_g  0.44    0.43   0.10  0.11   0.28   0.62    1.0     742.    1173.

Compare the model to the data

mcycle %>%
  mutate(Ef=mean(draws_gpbffg$f),
         sigma=mean(draws_gpbffg$sigma)) %>%  
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The MCMC integration works well and the model fit looks good.

Plot posterior draws and posterior mean of the mean function

draws_gpbffg %>%
  thin_draws(thin=5) %>%
  spread_rvars(f[i]) %>%
  unnest_rvars() %>%
  mutate(time=mcycle$times[i]) %>%
  ggplot(aes(x=time, y=f, group = .draw)) +
  geom_line(color=set1[2], alpha = 0.1) +
  geom_point(data=mcycle, mapping=aes(x=times,y=accel), inherit.aes=FALSE)+
  geom_line(data=mcycle, mapping=aes(x=times,y=mean(draws_gpbffg$f)),
            inherit.aes=FALSE, color=set1[1], size=1)+
  labs(x="Time (ms)", y="Acceleration (g)")

We can also plot the posterior draws of the latent functions, which is a good reminder that individual draws are more wiggly than the average of the draws, and thus show better also the uncertainty, for example, in the edge of the data.

Compare the posterior draws to the optimized parameters

odraws_gpbffg <- as_draws_df(opt_gpbffg$draws())
draws_gpbffg %>%
  thin_draws(thin=5) %>%
  as_draws_df() %>%
  ggplot(aes(x=lengthscale_f,y=sigma_f))+
  geom_point(color=set1[2])+
  geom_point(data=odraws_gpbffg,color=set1[1],size=4)+
  annotate("text",x=median(draws_gpbffg$lengthscale_f),
           y=max(draws_gpbffg$sigma_f)+0.1,
           label='Posterior draws',hjust=0.5,color=set1[2],size=6)+
  annotate("text",x=odraws_gpbffg$lengthscale_f+0.01,
           y=odraws_gpbffg$sigma_f,
           label='Optimized',hjust=0,color=set1[1],size=6)

Optimization result is far from being representative of the posterior.

GP model with Hilbert basis functions and Matern covariance

Exponentiated quadratic is sometimes considered to be too smooth as all the derivatives are continuos. For comparison we use Matern covariance. The Hilbert space basis functions are the same and only the spectral density values change (that is different basis functions have a different weighting).

Model code

file_gpbffg2 <- "gpbffg_matern.stan"
writeLines(readLines(file_gpbffg2))
functions {
#include gpbasisfun_functions.stan
}
data {
  int<lower=1> N;      // number of observations
  vector[N] x;         // univariate covariate
  vector[N] y;         // target variable
        
  real<lower=0> c_f;   // factor c to determine the boundary value L
  int<lower=1> M_f;    // number of basis functions
  real<lower=0> c_g;   // factor c to determine the boundary value L
  int<lower=1> M_g;    // number of basis functions
}
transformed data {
  // Normalize data
  real xmean = mean(x);
  real ymean = mean(y);
  real xsd = sd(x);
  real ysd = sd(y);
  vector[N] xn = (x - xmean)/xsd;
  vector[N] yn = (y - ymean)/ysd;
  // Basis functions for f
  real L_f = c_f*max(xn);
  matrix[N,M_f] PHI_f = PHI(N, M_f, L_f, xn);
  // Basis functions for g
  real L_g= c_g*max(xn);
  matrix[N,M_g] PHI_g = PHI(N, M_g, L_g, xn);
}
parameters {
  real intercept_f;
  real intercept_g;
  vector[M_f] beta_f;          // the basis functions coefficients
  vector[M_g] beta_g;          // the basis functions coefficients
  real<lower=0> lengthscale_f; // lengthscale of f
  real<lower=0> sigma_f;       // scale of f
  real<lower=0> lengthscale_g; // lengthscale of g
  real<lower=0> sigma_g;       // scale of g
}
model {
  // spectral densities for f and g
  vector[M_f] diagSPD_f = diagSPD_Matern(sigma_f, lengthscale_f, L_f, M_f);
  vector[M_g] diagSPD_g = diagSPD_Matern(sigma_g, lengthscale_g, L_g, M_g);
  // priors
  intercept_f ~ normal(0, 1);
  intercept_g ~ normal(0, 1);
  beta_f ~ normal(0, 1);
  beta_g ~ normal(0, 1);
  lengthscale_f ~ normal(0, 1);
  lengthscale_g ~ normal(0, 1);
  sigma_f ~ normal(0, .5);
  sigma_g ~ normal(0, .5);
  // model
  yn ~ normal(intercept_f + PHI_f * (diagSPD_f .* beta_f),
          exp(intercept_g + PHI_g * (diagSPD_g .* beta_g)));
}
generated quantities {
  vector[N] f;
  vector[N] sigma;
  {
    // spectral densities
    vector[M_f] diagSPD_f = diagSPD_Matern(sigma_f, lengthscale_f, L_f, M_f);
    vector[M_g] diagSPD_g = diagSPD_Matern(sigma_g, lengthscale_g, L_g, M_g);
    // function scaled back to the original scale
    f = (intercept_f + PHI_f * (diagSPD_f .* beta_f))*ysd + ymean;
    sigma = exp(intercept_g + PHI_g * (diagSPD_g .* beta_g))*ysd;
  }
}

Compile Stan model

model_gpbffg2 <- cmdstan_model(stan_file = file_gpbffg2, include_paths = ".")

Data to be passed to Stan

standata_gpbffg2 <- list(x=mcycle$times,
                        y=mcycle$accel,
                        N=length(mcycle$times),
                        c_f=1.5, # factor c of basis functions for GP for f1
                        M_f=40,  # number of basis functions for GP for f1
                        c_g=1.5, # factor c of basis functions for GP for g3
                        M_g=40)  # number of basis functions for GP for g3

Sample using dynamic HMC

fit_gpbffg2 <- model_gpbffg2$sample(data=standata_gpbffg2,
                                  iter_warmup=500, iter_sampling=500,
                                  chains=4, parallel_chains=4, adapt_delta=0.9)

Check whether parameters have reasonable values

draws_gpbffg2 <- as_draws_rvars(fit_gpbffg2$draws())
summarise_draws(subset(draws_gpbffg2,
                       variable=c('intercept','sigma_','lengthscale_'),
                       regex=TRUE))
# A tibble: 6 × 10
  variable         mean  median    sd   mad     q5    q95  rhat ess_bulk ess_tail
  <chr>           <dbl>   <dbl> <dbl> <dbl>  <dbl>  <dbl> <dbl>    <dbl>    <dbl>
1 intercept_f    0.0046  0.0037 0.040 0.040 -0.062  0.070   1.0    3095.    1150.
2 intercept_g   -1.2    -1.2    0.074 0.076 -1.3   -1.1     1.0    2002.    1369.
3 sigma_f        0.92    0.89   0.22  0.21   0.63   1.3     1.0    1787.    1469.
4 sigma_g        1.1     1.0    0.23  0.22   0.74   1.5     1.0    1739.    1643.
5 lengthscale_f  0.60    0.58   0.15  0.15   0.39   0.87    1.0    1621.    1659.
6 lengthscale_g  0.67    0.64   0.23  0.21   0.36   1.1     1.0    1399.    1541.

Compare the model to the data

mcycle %>%
  mutate(Ef=mean(draws_gpbffg2$f),
         sigma=mean(draws_gpbffg2$sigma)) %>%  
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The MCMC integration works well and the model fit looks good.

Plot posterior draws and posterior mean of the mean function

draws_gpbffg2 %>%
  thin_draws(thin=5) %>%
  spread_rvars(f[i]) %>%
  unnest_rvars() %>%
  mutate(time=mcycle$times[i]) %>%
  ggplot(aes(x=time, y=f, group = .draw)) +
  geom_line(color=set1[2], alpha = 0.1) +
  geom_point(data=mcycle, mapping=aes(x=times,y=accel), inherit.aes=FALSE)+
  geom_line(data=mcycle, mapping=aes(x=times,y=mean(draws_gpbffg2$f)),
            inherit.aes=FALSE, color=set1[1], size=1)+
  labs(x="Time (ms)", y="Acceleration (g)")

We see that when using Matern covariance instead of the exponentiated quadratic, the model fit is more wigggly.

IycgLS0tCiMnIHRpdGxlOiAiR2F1c3NpYW4gcHJvY2VzcyBkZW1vbnN0cmF0aW9uIHdpdGggU3RhbiIKIycgYXV0aG9yOiAiQWtpIFZlaHRhcmkiCiMnIGRhdGU6ICJGaXJzdCB2ZXJzaW9uIDIwMjEtMDEtMjguIExhc3QgbW9kaWZpZWQgYHIgZm9ybWF0KFN5cy5EYXRlKCkpYC4iCiMnIG91dHB1dDoKIycgICBodG1sX2RvY3VtZW50OgojJyAgICAgdGhlbWU6IHJlYWRhYmxlCiMnICAgICB0b2M6IHRydWUKIycgICAgIHRvY19kZXB0aDogMgojJyAgICAgdG9jX2Zsb2F0OiB0cnVlCiMnICAgICBjb2RlX2Rvd25sb2FkOiB0cnVlCiMnIC0tLQoKCiMnIERlbW9uc3RyYXRpb24gb2YgY292YXJpYW5jZSBtYXRyaXggYW5kIGJhc2lzIGZ1bmN0aW9uCiMnIGltcGxlbWVudGF0aW9uIG9mIEdhdXNzaWFuIHByb2Nlc3MgbW9kZWwgaW4gU3Rhbi4KIycKIycgVGhlIGJhc2ljcyBvZiB0aGUgY292YXJpYW5jZSBtYXRyaXggYXBwcm9hY2ggaXMgYmFzZWQgb24gdGhlIENoYXB0ZXIKIycgMTAgb2YgU3RhbiBVc2Vy4oCZcyBHdWlkZSwgVmVyc2lvbiAyLjI2IGJ5IFN0YW4gRGV2ZWxvcG1lbnQgVGVhbQojJyAoMjAyMSkuIGh0dHBzOi8vbWMtc3Rhbi5vcmcvZG9jcy9zdGFuLXVzZXJzLWd1aWRlLwojJwojJyBUaGUgYmFzaWNzIG9mIHRoZSBIaWxiZXJ0IHNwYWNlIGJhc2lzIGZ1bmN0aW9uIGFwcHJveGltYXRpb24gaXMKIycgYmFzZWQgb24gUml1dG9ydC1NYXlvbCwgQsO8cmtuZXIsIEFuZGVyc2VuLCBTb2xpbiwgYW5kIFZlaHRhcmkKIycgKDIwMjApLiBQcmFjdGljYWwgSGlsYmVydCBzcGFjZSBhcHByb3hpbWF0ZSBCYXllc2lhbiBHYXVzc2lhbgojJyBwcm9jZXNzZXMgZm9yIHByb2JhYmlsaXN0aWMgcHJvZ3JhbW1pbmcuIGh0dHBzOi8vYXJ4aXYub3JnL2Ficy8yMDA0LjExNDA4CiMnCiMnICMjIE1vdG9yY3ljbGUKIycgCiMnIERhdGEgYXJlIG1lYXN1cmVtZW50cyBvZiBoZWFkIGFjY2VsZXJhdGlvbiBpbiBhIHNpbXVsYXRlZAojJyBtb3RvcmN5Y2xlIGFjY2lkZW50LCB1c2VkIHRvIHRlc3QgY3Jhc2ggaGVsbWV0cy4KIycKIycgRGF0YSBhcmUgbW9kZWxsZWQgZmlyc3Qgd2l0aCBub3JtYWwgZGlzdHJpYnV0aW9uIGhhdmluZyBHYXVzc2lhbiBwcm9jZXNzCiMnIHByaW9yIG9uIG1lYW46CiMnICQkCiMnIHkgXHNpbSBcbWJveHtub3JtYWx9KGYoeCksIFxzaWdtYSlcXAojJyBmIFxzaW0gR1AoMCwgS18xKVxcCiMnIFxzaWdtYSBcc2ltIFxtYm94e25vcm1hbH1eeyt9KDAsIDEpLAojJyAkJAojJyBhbmQgdGhlbiB3aXRoIG5vcm1hbCBkaXN0cmlidXRpb24gaGF2aW5nIEdhdXNzaWFuIHByb2Nlc3MKIycgcHJpb3Igb24gbWVhbiBhbmQgbG9nIHN0YW5kYXJkIGRldmlhdGlvbjoKIycgJCQKIycgeSBcc2ltIFxtYm94e25vcm1hbH0oZih4KSwgXGV4cChnKHgpKVxcCiMnIGYgXHNpbSBHUCgwLCBLXzEpXFwKIycgZyBcc2ltIEdQKDAsIEtfMikuCiMnICQkCiMnCgojKyBzZXR1cCwgaW5jbHVkZT1GQUxTRQprbml0cjo6b3B0c19jaHVuayRzZXQobWVzc2FnZT1GQUxTRSwgZXJyb3I9RkFMU0UsIHdhcm5pbmc9RkFMU0UsIGNvbW1lbnQ9TkEsIGNhY2hlPUZBTFNFKQoKIycgIyMjIyBMb2FkIHBhY2thZ2VzCmxpYnJhcnkoY21kc3RhbnIpIApsaWJyYXJ5KHBvc3RlcmlvcikKbGlicmFyeSh0aWR5YmF5ZXMpCm9wdGlvbnMocGlsbGFyLm5lZyA9IEZBTFNFLCBwaWxsYXIuc3VidGxlPUZBTFNFLCBwaWxsYXIuc2lnZmlnPTIpCmxpYnJhcnkodGlkeXIpIApsaWJyYXJ5KGRwbHlyKSAKbGlicmFyeShnZ3Bsb3QyKQpsaWJyYXJ5KGJheWVzcGxvdCkKdGhlbWVfc2V0KGJheWVzcGxvdDo6dGhlbWVfZGVmYXVsdChiYXNlX2ZhbWlseSA9ICJzYW5zIiwgYmFzZV9zaXplPTE2KSkKc2V0MSA8LSBSQ29sb3JCcmV3ZXI6OmJyZXdlci5wYWwoNywgIlNldDEiKQpTRUVEIDwtIDQ4OTI3ICMgc2V0IHJhbmRvbSBzZWVkIGZvciByZXByb2R1Y2liaWxpdHkKCiMnICMjIE1vdG9yY3ljbGUgYWNjaWRlbnQgYWNjZWxlcmF0aW9uIGRhdGEKIycgCiMnIExvYWQgZGF0YQpkYXRhKG1jeWNsZSwgcGFja2FnZT0iTUFTUyIpCmhlYWQobWN5Y2xlKQoKIycgUGxvdCBkYXRhCm1jeWNsZSAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKQoKIycgIyMgR1AgbW9kZWwgd2l0aCBob21vc2tlZGFzdGljIHJlc2lkdWFsCiMnCiMnIFdlIHN0YXJ0IHdpdGggYSBzaW1wbGVyIGhvbW9za2VkYXN0aWMgcmVzaWR1YWwgR2F1c3NpYW4gcHJvY2VzcyBtb2RlbAojJyAkJAojJyB5IFxzaW0gXG1ib3h7bm9ybWFsfShmKHgpLCBcc2lnbWEpXFwKIycgZiBcc2ltIEdQKDAsIEtfMSlcXAojJyBcc2lnbWEgXHNpbSBub3JtYWxeeyt9KDAsIDEpLAojJyAkJAojJyB0aGF0IGhhcyBhbmFseXRpYyBtYXJnaW5hbCBsaWtlbGlob29kIGZvciB0aGUgY292YXJpYW5jZSBmdW5jdGlvbgojJyBhbmQgcmVzaWR1YWwgc2NhbGUgcGFyYW1ldGVycy4KIycgCgojJyBNb2RlbCBjb2RlCmZpbGVfZ3Bjb3ZmIDwtICJncGNvdmYuc3RhbiIKd3JpdGVMaW5lcyhyZWFkTGluZXMoZmlsZV9ncGNvdmYpKQoKIycgQ29tcGlsZSBTdGFuIG1vZGVsCm1vZGVsX2dwY292ZiA8LSBjbWRzdGFuX21vZGVsKHN0YW5fZmlsZSA9IGZpbGVfZ3Bjb3ZmKQoKIycgRGF0YSB0byBiZSBwYXNzZWQgdG8gU3RhbgpzdGFuZGF0YV9ncGNvdmYgPC0gbGlzdCh4PW1jeWNsZSR0aW1lcywKICAgICAgICAgICAgICAgICAgICAgICAgeDI9bWN5Y2xlJHRpbWVzLAogICAgICAgICAgICAgICAgICAgICAgICB5PW1jeWNsZSRhY2NlbCwKICAgICAgICAgICAgICAgICAgICAgICAgTj1sZW5ndGgobWN5Y2xlJHRpbWVzKSwKICAgICAgICAgICAgICAgICAgICAgICAgTjI9bGVuZ3RoKG1jeWNsZSR0aW1lcykpCgojJyBPcHRpbWl6ZSBhbmQgZmluZCBNQVAgZXN0aW1hdGUKIysgb3B0X2dwY292ZiwgcmVzdWx0cz0naGlkZScKb3B0X2dwY292ZiA8LSBtb2RlbF9ncGNvdmYkb3B0aW1pemUoZGF0YT1zdGFuZGF0YV9ncGNvdmYsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGluaXQ9MC4xLCBhbGdvcml0aG09J2JmZ3MnKQoKIycgQ2hlY2sgd2hldGhlciBwYXJhbWV0ZXJzIGhhdmUgcmVhc29uYWJsZSB2YWx1ZXMKb2RyYXdzX2dwY292ZiA8LSBhc19kcmF3c19ydmFycyhvcHRfZ3Bjb3ZmJGRyYXdzKCkpCnN1YnNldChvZHJhd3NfZ3Bjb3ZmLCB2YXJpYWJsZT1jKCdzaWdtYV8nLCdsZW5ndGhzY2FsZV8nLCdzaWdtYScpLCByZWdleD1UUlVFKQoKIycgQ29tcGFyZSB0aGUgbW9kZWwgdG8gdGhlIGRhdGEKbWN5Y2xlICU+JQogIG11dGF0ZShFZj1tZWFuKG9kcmF3c19ncGNvdmYkZiksCiAgICAgICAgIHNpZ21hPW1lYW4ob2RyYXdzX2dwY292ZiRzaWdtYSkpICU+JSAgCiAgZ2dwbG90KGFlcyh4PXRpbWVzLHk9YWNjZWwpKSsKICBnZW9tX3BvaW50KCkrCiAgbGFicyh4PSJUaW1lIChtcykiLCB5PSJBY2NlbGVyYXRpb24gKGcpIikrCiAgZ2VvbV9saW5lKGFlcyh5PUVmKSwgY29sb3I9c2V0MVsxXSkrCiAgZ2VvbV9saW5lKGFlcyh5PUVmLTIqc2lnbWEpLCBjb2xvcj1zZXQxWzFdLGxpbmV0eXBlPSJkYXNoZWQiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYrMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpCgojJyBUaGUgbW9kZWwgZml0IGdpdmVuIG9wdGltaXplZCBwYXJhbWV0ZXJzLCBsb29rcyByZWFzb25hYmxlCiMnIGNvbnNpZGVyaW5nIHRoZSB1c2Ugb2YgaG9tb3NrZWRhc3RpYyByZXNpZHVhbCBtb2RlbC4KIycgCiMnIFNhbXBsZSB1c2luZyBkeW5hbWljIEhNQwojKyBmaXRfZ3Bjb3ZmLCByZXN1bHRzPSdoaWRlJwpmaXRfZ3Bjb3ZmIDwtIG1vZGVsX2dwY292ZiRzYW1wbGUoZGF0YT1zdGFuZGF0YV9ncGNvdmYsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpdGVyX3dhcm11cD01MDAsIGl0ZXJfc2FtcGxpbmc9NTAwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY2hhaW5zPTQsIHBhcmFsbGVsX2NoYWlucz00LCByZWZyZXNoPTEwMCkKCiMnIENoZWNrIHdoZXRoZXIgcGFyYW1ldGVycyBoYXZlIHJlYXNvbmFibGUgdmFsdWVzCmRyYXdzX2dwY292ZiA8LSBhc19kcmF3c19ydmFycyhmaXRfZ3Bjb3ZmJGRyYXdzKCkpCnN1bW1hcmlzZV9kcmF3cyhzdWJzZXQoZHJhd3NfZ3Bjb3ZmLAogICAgICAgICAgICAgICAgICAgICAgIHZhcmlhYmxlPWMoJ3NpZ21hXycsJ2xlbmd0aHNjYWxlXycsJ3NpZ21hJyksCiAgICAgICAgICAgICAgICAgICAgICAgcmVnZXg9VFJVRSkpCgojJyBDb21wYXJlIHRoZSBtb2RlbCB0byB0aGUgZGF0YQptY3ljbGUgJT4lCiAgbXV0YXRlKEVmPW1lYW4oZHJhd3NfZ3Bjb3ZmJGYpLAogICAgICAgICBzaWdtYT1tZWFuKGRyYXdzX2dwY292ZiRzaWdtYSkpICU+JSAgCiAgZ2dwbG90KGFlcyh4PXRpbWVzLHk9YWNjZWwpKSsKICBnZW9tX3BvaW50KCkrCiAgbGFicyh4PSJUaW1lIChtcykiLCB5PSJBY2NlbGVyYXRpb24gKGcpIikrCiAgZ2VvbV9saW5lKGFlcyh5PUVmKSwgY29sb3I9c2V0MVsxXSkrCiAgZ2VvbV9saW5lKGFlcyh5PUVmLTIqc2lnbWEpLCBjb2xvcj1zZXQxWzFdLGxpbmV0eXBlPSJkYXNoZWQiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYrMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpCgojJyBUaGUgbW9kZWwgZml0IGdpdmVuIGludGVncmF0ZWQgcGFyYW1ldGVycyBsb29rcyBzaW1pbGFyIHRvIHRoZQojJyBvcHRpbWl6ZWQgb25lLgojJyAKIycgQ29tcGFyZSB0aGUgcG9zdGVyaW9yIGRyYXdzIHRvIHRoZSBvcHRpbWl6ZWQgcGFyYW1ldGVycwpvZHJhd3NfZ3Bjb3ZmIDwtIGFzX2RyYXdzX2RmKG9wdF9ncGNvdmYkZHJhd3MoKSkKZHJhd3NfZ3Bjb3ZmICU+JQogIGFzX2RyYXdzX2RmKCkgJT4lCiAgZ2dwbG90KGFlcyh4PWxlbmd0aHNjYWxlX2YseT1zaWdtYV9mKSkrCiAgZ2VvbV9wb2ludChjb2xvcj1zZXQxWzJdKSsKICBnZW9tX3BvaW50KGRhdGE9b2RyYXdzX2dwY292Zixjb2xvcj1zZXQxWzFdLHNpemU9NCkrCiAgYW5ub3RhdGUoInRleHQiLHg9bWVkaWFuKGRyYXdzX2dwY292ZiRsZW5ndGhzY2FsZV9mKSwKICAgICAgICAgICB5PW1heChkcmF3c19ncGNvdmYkc2lnbWFfZikrMC4xLAogICAgICAgICAgIGxhYmVsPSdQb3N0ZXJpb3IgZHJhd3MnLGhqdXN0PTAuNSxjb2xvcj1zZXQxWzJdLHNpemU9NikrCiAgYW5ub3RhdGUoInRleHQiLHg9b2RyYXdzX2dwY292ZiRsZW5ndGhzY2FsZV9mKzAuMDEsCiAgICAgICAgICAgeT1vZHJhd3NfZ3Bjb3ZmJHNpZ21hX2YsCiAgICAgICAgICAgbGFiZWw9J09wdGltaXplZCcsaGp1c3Q9MCxjb2xvcj1zZXQxWzFdLHNpemU9NikKCiMnIFRoZSBvcHRpbWl6YXRpb24gcmVzdWx0IGlzIGluIHRoZSBtaWRkbGUgb2YgdGhlIHBvc3RlcmlvciBhbmQgcXVpdGUKIycgd2VsbCByZXByZXNlbnRhdGl2ZSBvZiB0aGUgbG93IGRpbWVuc2lvbmFsIHBvc3RlcmlvciAoaW4gaGlnaGVyCiMnIGRpbWVuc2lvbnMgdGhlIG1lYW4gb3IgbW9kZSBvZiB0aGUgcG9zdGVyaW9yIGlzIG5vdCBsaWtlbHkgdG8gYmUKIycgcmVwcmVzZW50YXRpdmUpLgojJyAKIycgQ29tcGFyZSBvcHRpbWl6ZWQgYW5kIHBvc3RlcmlvciBwcmVkaWN0aXZlIGRpc3RyaWJ1dGlvbnMKb2RyYXdzX2dwY292ZiA8LSBhc19kcmF3c19ydmFycyhvcHRfZ3Bjb3ZmJGRyYXdzKCkpCm1jeWNsZSAlPiUKICBtdXRhdGUoRWY9bWVhbihkcmF3c19ncGNvdmYkZiksCiAgICAgICAgIHNpZ21hPW1lYW4oZHJhd3NfZ3Bjb3ZmJHNpZ21hKSwKICAgICAgICAgRWZvPW1lYW4ob2RyYXdzX2dwY292ZiRmKSwKICAgICAgICAgc2lnbWFvPW1lYW4ob2RyYXdzX2dwY292ZiRzaWdtYSkpICU+JQogIGdncGxvdChhZXMoeD10aW1lcyx5PWFjY2VsKSkrCiAgZ2VvbV9wb2ludCgpKwogIGxhYnMoeD0iVGltZSAobXMpIiwgeT0iQWNjZWxlcmF0aW9uIChnKSIpKwogIGdlb21fbGluZShhZXMoeT1FZiksIGNvbG9yPXNldDFbMV0pKwogIGdlb21fbGluZShhZXMoeT1FZi0yKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikrCiAgZ2VvbV9saW5lKGFlcyh5PUVmKzIqc2lnbWEpLCBjb2xvcj1zZXQxWzFdLGxpbmV0eXBlPSJkYXNoZWQiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWZvKSwgY29sb3I9c2V0MVsyXSkrCiAgZ2VvbV9saW5lKGFlcyh5PUVmby0yKnNpZ21hbyksIGNvbG9yPXNldDFbMl0sbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShhZXMoeT1FZm8rMipzaWdtYW8pLCBjb2xvcj1zZXQxWzJdLGxpbmV0eXBlPSJkYXNoZWQiKQoKIycgVGhlIG1vZGVsIHByZWRpY3Rpb25zIGFyZSB2ZXJ5IHNpbWlsYXIsIGFuZCBpbiBnZW5lcmFsIEdQCiMnIGNvdmFyaWFuY2UgZnVuY3Rpb24gYW5kIG9ic2VydmF0aW9uIG1vZGVsIHBhcmFtZXRlcnMgY2FuIGJlIHF1aXRlCiMnIHNhZmVseSBvcHRpbWl6ZWQgaWYgdGhlcmUgYXJlIG9ubHkgYSBmZXcgb2YgdGhlbSBhbmQgdGh1cyBtYXJnaW5hbAojJyBwb3N0ZXJpb3IgaXMgbG93IGRpbWVuc2lvbmFsIGFuZCB0aGUgbnVtYmVyIG9mIG9ic2VydmF0aW9ucyBpcwojJyByZWxhdGl2ZWx5IGhpZ2guCiMnIAojJyAjIyMgMTAlIG9mIGRhdGEKIycKIycgVG8gZGVtb25zdHJhdGUgdGhhdCB0aGUgb3B0aW1pemF0aW9uIGlzIG5vdCBhbHdheXMgc2FmZSwgd2UgdXNlCiMnIG9ubHkgMTAlIG9mIHRoZSBkYXRhIGZvciBtb2RlbCBmaXR0aW5nLgojJyAKIycgRGF0YSB0byBiZSBwYXNzZWQgdG8gU3RhbgptY3ljbGVfMTBwIDwtIG1jeWNsZVtzZXEoMSwxMzMsYnk9MTApLF0Kc3RhbmRhdGFfMTBwIDwtIGxpc3QoeD1tY3ljbGVfMTBwJHRpbWVzLAogICAgICAgICAgICAgICAgICAgICB4Mj1tY3ljbGUkdGltZXMsCiAgICAgICAgICAgICAgICAgICAgIHk9bWN5Y2xlXzEwcCRhY2NlbCwKICAgICAgICAgICAgICAgICAgICAgTj1sZW5ndGgobWN5Y2xlXzEwcCR0aW1lcyksCiAgICAgICAgICAgICAgICAgICAgIE4yPWxlbmd0aChtY3ljbGUkdGltZXMpKQoKIycgT3B0aW1pemUgYW5kIGZpbmQgTUFQIGVzdGltYXRlCiMrIG9wdF8xMHAsIHJlc3VsdHM9J2hpZGUnCm9wdF8xMHAgPC0gbW9kZWxfZ3Bjb3ZmJG9wdGltaXplKGRhdGE9c3RhbmRhdGFfMTBwLCBpbml0PTAuMSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYWxnb3JpdGhtPSdsYmZncycpCgojJyBDaGVjayB3aGV0aGVyIHBhcmFtZXRlcnMgaGF2ZSByZWFzb25hYmxlIHZhbHVlcwpvZHJhd3NfMTBwIDwtIGFzX2RyYXdzX3J2YXJzKG9wdF8xMHAkZHJhd3MoKSkKc3Vic2V0KG9kcmF3c18xMHAsIHZhcmlhYmxlPWMoJ3NpZ21hXycsJ2xlbmd0aHNjYWxlXycsJ3NpZ21hJyksIHJlZ2V4PVRSVUUpCgojJyBDb21wYXJlIHRoZSBtb2RlbCB0byB0aGUgZGF0YQptY3ljbGVfMTBwICU+JQogIGdncGxvdChhZXMoeD10aW1lcyx5PWFjY2VsKSkrCiAgZ2VvbV9wb2ludCgpKwogIGxhYnMoeD0iVGltZSAobXMpIiwgeT0iQWNjZWxlcmF0aW9uIChnKSIpKwogIGdlb21fbGluZShkYXRhPW1jeWNsZSxhZXMoeD10aW1lcyx5PW1lYW4ob2RyYXdzXzEwcCRmKSksIGNvbG9yPXNldDFbMV0pKwogIGdlb21fbGluZShkYXRhPW1jeWNsZSxhZXMoeD10aW1lcyx5PW1lYW4ob2RyYXdzXzEwcCRmLTIqb2RyYXdzXzEwcCRzaWdtYSkpLCBjb2xvcj1zZXQxWzFdLAogICAgICAgICAgICBsaW5ldHlwZT0iZGFzaGVkIikrCiAgZ2VvbV9saW5lKGRhdGE9bWN5Y2xlLGFlcyh4PXRpbWVzLHk9bWVhbihvZHJhd3NfMTBwJGYrMipvZHJhd3NfMTBwJHNpZ21hKSksIGNvbG9yPXNldDFbMV0sCiAgICAgICAgICAgIGxpbmV0eXBlPSJkYXNoZWQiKQoKIycgVGhlIG1vZGVsIGZpdCBpcyBjbGVhcmx5IG92ZXItZml0dGVkIGFuZCBvdmVyLWNvbmZpZGVudC4KIycgCiMnIFNhbXBsZSB1c2luZyBkeW5hbWljIEhNQwojKyBmaXRfMTBwLCByZXN1bHRzPSdoaWRlJwpmaXRfMTBwIDwtIG1vZGVsX2dwY292ZiRzYW1wbGUoZGF0YT1zdGFuZGF0YV8xMHAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpdGVyX3dhcm11cD0xMDAwLCBpdGVyX3NhbXBsaW5nPTEwMDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBhZGFwdF9kZWx0YT0wLjk1LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY2hhaW5zPTQsIHBhcmFsbGVsX2NoYWlucz00LCByZWZyZXNoPTEwMCkKCiMnIENoZWNrIHdoZXRoZXIgcGFyYW1ldGVycyBoYXZlIHJlYXNvbmFibGUgdmFsdWVzCmRyYXdzXzEwcCA8LSBhc19kcmF3c19ydmFycyhmaXRfMTBwJGRyYXdzKCkpCnN1bW1hcmlzZV9kcmF3cyhzdWJzZXQoZHJhd3NfMTBwLCB2YXJpYWJsZT1jKCdzaWdtYV8nLCdsZW5ndGhzY2FsZV8nLCdzaWdtYScpLAogICAgICAgICAgICAgICAgICAgICAgIHJlZ2V4PVRSVUUpKQoKIycgQ29tcGFyZSB0aGUgbW9kZWwgdG8gdGhlIGRhdGEKbWN5Y2xlXzEwcCAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKSsKICBnZW9tX2xpbmUoZGF0YT1tY3ljbGUsYWVzKHg9dGltZXMseT1tZWFuKGRyYXdzXzEwcCRmKSksIGNvbG9yPXNldDFbMV0pKwogIGdlb21fbGluZShkYXRhPW1jeWNsZSxhZXMoeD10aW1lcyx5PW1lYW4oZHJhd3NfMTBwJGYtMipkcmF3c18xMHAkc2lnbWEpKSwgY29sb3I9c2V0MVsxXSwKICAgICAgICAgICAgbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShkYXRhPW1jeWNsZSxhZXMoeD10aW1lcyx5PW1lYW4oZHJhd3NfMTBwJGYrMipkcmF3c18xMHAkc2lnbWEpKSwgY29sb3I9c2V0MVsxXSwKICAgICAgICAgICAgbGluZXR5cGU9ImRhc2hlZCIpCgojJyBUaGUgcG9zdGVyaW9yIHByZWRpY3RpdmUgZGlzdHJpYnV0aW9uIGlzIG11Y2ggbW9yZSBjb25zZXJ2YXRpdmUgYW5kCiMnIHNob3dzIHRoZSB1bmNlcnRhaW50eSBkdWUgdG8gaGF2aW5nIG9ubHkgYSBzbWFsbCBudW1iZXIgb2YKIycgb2JzZXJ2YXRpb25zLgojJyAKIycgQ29tcGFyZSB0aGUgcG9zdGVyaW9yIGRyYXdzIHRvIHRoZSBvcHRpbWl6ZWQgcGFyYW1ldGVycwpvZHJhd3NfMTBwIDwtIGFzX2RyYXdzX2RmKG9wdF8xMHAkZHJhd3MoKSkKZHJhd3NfMTBwICU+JQogIHRoaW5fZHJhd3ModGhpbj01KSAlPiUKICBhc19kcmF3c19kZigpICU+JQogIGdncGxvdChhZXMoeD1zaWdtYSx5PXNpZ21hX2YpKSsKICBnZW9tX3BvaW50KGNvbG9yPXNldDFbMl0pKwogIGdlb21fcG9pbnQoZGF0YT1vZHJhd3NfMTBwLGNvbG9yPXNldDFbMV0sc2l6ZT00KSsKICBhbm5vdGF0ZSgidGV4dCIseD1tZWRpYW4oZHJhd3NfMTBwJHNpZ21hKSwKICAgICAgICAgICB5PW1heChkcmF3c18xMHAkc2lnbWFfZikrMC4xLAogICAgICAgICAgIGxhYmVsPSdQb3N0ZXJpb3IgZHJhd3MnLGhqdXN0PTAuNSxjb2xvcj1zZXQxWzJdLHNpemU9NikrCiAgYW5ub3RhdGUoInRleHQiLHg9b2RyYXdzXzEwcCRzaWdtYSswLjAxLAogICAgICAgICAgIHk9b2RyYXdzXzEwcCRzaWdtYV9mLAogICAgICAgICAgIGxhYmVsPSdPcHRpbWl6ZWQnLGhqdXN0PTAsY29sb3I9c2V0MVsxXSxzaXplPTYpCgojJyBUaGUgb3B0aW1pemF0aW9uIHJlc3VsdCBpcyBpbiB0aGUgZWRnZSBvZiB0aGUgcG9zdGVyaW9yIGNsb3NlIHRvCiMnIHplcm8gcmVzaWR1YWwgc2NhbGUuIFdoaWxlIHRoZXJlIGFyZSBwb3N0ZXJpb3IgZHJhd3MgY2xvc2UgdG8gemVybywKIycgaW50ZWdyYXRpbmcgb3ZlciB0aGUgd2lkZSBwb3N0ZXJpb3IgdGFrZXMgaW50byBhY2NvdW50IHRoZQojJyB1bmNlcnRhaW50eSBhbmQgdGhlIHByZWRpY3Rpb25zIHRodXMgYXJlIG1vcmUgdW5jZXJ0YWluLCB0b28uCiMnIAojJyBDb21wYXJlIG9wdGltaXplZCBhbmQgcG9zdGVyaW9yIHByZWRpY3RpdmUgZGlzdHJpYnV0aW9ucwpvZHJhd3NfMTBwIDwtIGFzX2RyYXdzX3J2YXJzKG9wdF8xMHAkZHJhd3MoKSkKbWN5Y2xlICU+JQogIG11dGF0ZShFZj1tZWFuKGRyYXdzXzEwcCRmKSwKICAgICAgICAgc2lnbWE9bWVhbihkcmF3c18xMHAkc2lnbWEpLAogICAgICAgICBFZm89bWVhbihvZHJhd3NfMTBwJGYpLAogICAgICAgICBzaWdtYW89bWVhbihvZHJhd3NfMTBwJHNpZ21hKSkgJT4lCiAgZ2dwbG90KGFlcyh4PXRpbWVzLHk9YWNjZWwpKSsKICBnZW9tX3BvaW50KCkrCiAgbGFicyh4PSJUaW1lIChtcykiLCB5PSJBY2NlbGVyYXRpb24gKGcpIikrCiAgZ2VvbV9saW5lKGFlcyh5PUVmKSwgY29sb3I9c2V0MVsxXSkrCiAgZ2VvbV9saW5lKGFlcyh5PUVmLTIqc2lnbWEpLCBjb2xvcj1zZXQxWzFdLGxpbmV0eXBlPSJkYXNoZWQiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYrMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShhZXMoeT1FZm8pLCBjb2xvcj1zZXQxWzJdKSsKICBnZW9tX2xpbmUoYWVzKHk9RWZvLTIqc2lnbWFvKSwgY29sb3I9c2V0MVsyXSxsaW5ldHlwZT0iZGFzaGVkIikrCiAgZ2VvbV9saW5lKGFlcyh5PUVmbysyKnNpZ21hbyksIGNvbG9yPXNldDFbMl0sbGluZXR5cGU9ImRhc2hlZCIpCgojJyBUaGUgZmlndXJlIHNob3dzIHRoZSBtb2RlbCBwcmVkaWN0aW9uIGdpdmVuIDEwJSBvZiBkYXRhLCBidXQgYWxzbwojJyB0aGUgZnVsbCBkYXRhIGFzIHRlc3QgZGF0YS4gVGhlIG9wdGltaXplZCBtb2RlbCBpcyBvdmVyLWZpdHRlZCBhbmQKIycgb3ZlcmNvbmZpZGVudC4gRXZlbiBpZiB0aGUgaG9tb3NrZWRhc3RpYyByZXNpZHVhbCBpcyB3cm9uZyBoZXJlLAojJyB0aGUgcG9zdGVyaW9yIHByZWRpY3RpdmUgaW50ZXJ2YWwgY292ZXJzIG1vc3Qgb2YgdGhlIG9ic2VydmF0aW9uCiMnIChhbmQgaW4gY2FzZSBvZiBnb29kIGNhbGlicmF0aW9uIHNob3VsZCBub3QgY292ZXIgdGhlbSBhbGwpLgojJyAKCiMnICMjIEdQIHdpdGggY292YXJpYW5jZSBtYXRyaWNlcwojJwojJyBXZSBuZXh0IG1ha2UgYSBtb2RlbCB3aXRoIGhldGVyb3NrZWRhc3RpYyByZXNpZHVhbCBtb2RlbCB1c2luZwojJyBHYXVzc2lhbiBwcm9jZXNzIHByaW9yIGFsc28gZm9yIHRoZSBsb2dhcml0aG0gb2YgdGhlIHJlc2lkdWFsCiMnIHNjYWxlOgojJyAkJAojJyB5IFxzaW0gXG1ib3h7bm9ybWFsfShmKHgpLCBcZXhwKGcoeCkpXFwKIycgZiBcc2ltIEdQKDAsIEtfMSlcXAojJyBnIFxzaW0gR1AoMCwgS18yKS4KIycgJCQKIycKIycgTm93IHRoZXJlIGlzIG5vIGFuYWx5dGljYWwgc29sdXRpb24gYXMgR1AgcHJpb3IgdGhyb3VnaCB0aGUKIycgZXhwb25lbnRpYWwgZnVuY3Rpb24gaXMgbm90IGEgY29uanVnYXRlIHByaW9yLiBJbiB0aGlzIGNhc2Ugd2UKIycgcHJlc2VudCB0aGUgbGF0ZW50IHZhbHVlcyBvZiBmIGFuZCBnIGV4cGxpY2l0bHkgYW5kIHNhbXBsZSBmcm9tIHRoZQojJyBqb2ludCBwb3N0ZXJpb3Igb2YgdGhlIGNvdmFyaWFuY2UgZnVuY3Rpb24gcGFyYW1ldGVycywgYW5kIHRoZQojJyBsYXRlbnQgdmFsdWVzLiBJdCB3b3VsZCBiZSBwb3NzaWJsZSBhbHNvIHRvIHVzZSBMYXBsYWNlLAojJyB2YXJpYXRpb25hbCBpbmZlcmVuY2UsIG9yIGV4cGVjdGF0aW9uIHByb3BhZ2F0aW9uIHRvIGludGVncmF0ZSBvdmVyCiMnIHRoZSBsYXRlbnQgdmFsdWVzLCBidXQgdGhhdCBpcyBhbm90aGVyIHN0b3J5LgojJyAKIycgTW9kZWwgY29kZQpmaWxlX2dwY292ZmcgPC0gImdwY292Zmcuc3RhbiIKd3JpdGVMaW5lcyhyZWFkTGluZXMoZmlsZV9ncGNvdmZnKSkKCiMnIENvbXBpbGUgU3RhbiBtb2RlbAptb2RlbF9ncGNvdmZnIDwtIGNtZHN0YW5fbW9kZWwoc3Rhbl9maWxlID0gZmlsZV9ncGNvdmZnKQoKIycgRGF0YSB0byBiZSBwYXNzZWQgdG8gU3RhbgpzdGFuZGF0YV9ncGNvdmZnIDwtIGxpc3QoeD1tY3ljbGUkdGltZXMsCiAgICAgICAgICAgICAgICAgICAgICAgICB5PW1jeWNsZSRhY2NlbCwKICAgICAgICAgICAgICAgICAgICAgICAgIE49bGVuZ3RoKG1jeWNsZSR0aW1lcykpCgojJyBPcHRpbWl6ZSBhbmQgZmluZCBNQVAgZXN0aW1hdGUKIysgb3B0X2dwY292ZmcsIHJlc3VsdHM9J2hpZGUnCm9wdF9ncGNvdmZnIDwtIG1vZGVsX2dwY292Zmckb3B0aW1pemUoZGF0YT1zdGFuZGF0YV9ncGNvdmZnLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGluaXQ9MC4xLCBhbGdvcml0aG09J2JmZ3MnKQoKIycgQ2hlY2sgd2hldGhlciBwYXJhbWV0ZXJzIGhhdmUgcmVhc29uYWJsZSB2YWx1ZXMKb2RyYXdzX2dwY292ZmcgPC0gYXNfZHJhd3NfcnZhcnMob3B0X2dwY292ZmckZHJhd3MoKSkKc3Vic2V0KG9kcmF3c19ncGNvdmZnLCB2YXJpYWJsZT1jKCdzaWdtYV8nLCdsZW5ndGhzY2FsZV8nKSwgcmVnZXg9VFJVRSkKCiMnIENvbXBhcmUgdGhlIG1vZGVsIHRvIHRoZSBkYXRhCm1jeWNsZSAlPiUKICBtdXRhdGUoRWYgPSBtZWFuKG9kcmF3c19ncGNvdmZnJGYpLAogICAgICAgICBzaWdtYSA9IG1lYW4ob2RyYXdzX2dwY292Zmckc2lnbWEpKSAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYpLCBjb2xvcj1zZXQxWzFdKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYtMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShhZXMoeT1FZisyKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikKCiMnIFRoZSBvcHRpbWl6YXRpb24gb3ZlcmZpdHMsIGFzIHdlIGFyZSBub3cgb3B0aW1pemluZyB0aGUgam9pbnQKIycgcG9zdGVyaW9yIG9mIDIgY292YXJpYW5jZSBmdW5jdGlvbiBwYXJhbWV0ZXJzIGFuZCAyIHggMTMzIGxhdGVudAojJyB2YWx1ZXMuCiMnIAojJyBTYW1wbGUgdXNpbmcgZHluYW1pYyBITUMKIysgZml0X2dwY292ZmcsIHJlc3VsdHM9J2hpZGUnCmZpdF9ncGNvdmZnIDwtIG1vZGVsX2dwY292Zmckc2FtcGxlKGRhdGE9c3RhbmRhdGFfZ3Bjb3ZmZywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaXRlcl93YXJtdXA9MTAwLCBpdGVyX3NhbXBsaW5nPTEwMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY2hhaW5zPTQsIHBhcmFsbGVsX2NoYWlucz00LCByZWZyZXNoPTEwKQoKIycgQ2hlY2sgd2hldGhlciBwYXJhbWV0ZXJzIGhhdmUgcmVhc29uYWJsZSB2YWx1ZXMKZHJhd3NfZ3Bjb3ZmZyA8LSBhc19kcmF3c19ydmFycyhmaXRfZ3Bjb3ZmZyRkcmF3cygpKQpzdW1tYXJpc2VfZHJhd3Moc3Vic2V0KGRyYXdzX2dwY292ZmcsIHZhcmlhYmxlPWMoJ3NpZ21hXycsJ2xlbmd0aHNjYWxlXycpLAogICAgICAgICAgICAgICAgICAgICAgIHJlZ2V4PVRSVUUpKQoKIycgQ29tcGFyZSB0aGUgbW9kZWwgdG8gdGhlIGRhdGEKbWN5Y2xlICU+JQogIG11dGF0ZShFZiA9IG1lYW4oZHJhd3NfZ3Bjb3ZmZyRmKSwKICAgICAgICAgc2lnbWEgPSBtZWFuKGRyYXdzX2dwY292Zmckc2lnbWEpKSAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYpLCBjb2xvcj1zZXQxWzFdKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYtMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShhZXMoeT1FZisyKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikKCiMnIFRoZSBNQ01DIGludGVncmF0aW9uIHdvcmtzIHdlbGwgYW5kIHRoZSBtb2RlbCBmaXQgbG9va3MgZ29vZC4KIycgCiMnIFBsb3QgcG9zdGVyaW9yIGRyYXdzIGFuZCBwb3N0ZXJpb3IgbWVhbiBvZiB0aGUgbWVhbiBmdW5jdGlvbgpkcmF3c19ncGNvdmZnICU+JQogIHRoaW5fZHJhd3ModGhpbj01KSAlPiUKICBzcHJlYWRfcnZhcnMoZltpXSkgJT4lCiAgdW5uZXN0X3J2YXJzKCkgJT4lCiAgbXV0YXRlKHRpbWU9bWN5Y2xlJHRpbWVzW2ldKSAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZSwgeT1mLCBncm91cCA9IC5kcmF3KSkgKwogIGdlb21fbGluZShjb2xvcj1zZXQxWzJdLCBhbHBoYSA9IDAuMSkgKwogIGdlb21fcG9pbnQoZGF0YT1tY3ljbGUsIG1hcHBpbmc9YWVzKHg9dGltZXMseT1hY2NlbCksIGluaGVyaXQuYWVzPUZBTFNFKSArCiAgZ2VvbV9saW5lKGRhdGE9bWN5Y2xlLCBtYXBwaW5nPWFlcyh4PXRpbWVzLHk9bWVhbihkcmF3c19ncGNvdmZnJGYpKSwKICAgICAgICAgICAgaW5oZXJpdC5hZXM9RkFMU0UsIGNvbG9yPXNldDFbMV0sIHNpemU9MSkrCiAgbGFicyh4PSJUaW1lIChtcykiLCB5PSJBY2NlbGVyYXRpb24gKGcpIikKCiMnIFdlIGNhbiBhbHNvIHBsb3QgdGhlIHBvc3RlcmlvciBkcmF3cyBvZiB0aGUgbGF0ZW50IGZ1bmN0aW9ucywgd2hpY2gKIycgaXMgYSBnb29kIHJlbWluZGVyIHRoYXQgaW5kaXZpZHVhbCBkcmF3cyBhcmUgbW9yZSB3aWdnbHkgdGhhbiB0aGUKIycgYXZlcmFnZSBvZiB0aGUgZHJhd3MsIGFuZCB0aHVzIHNob3cgYmV0dGVyIGFsc28gdGhlIHVuY2VydGFpbnR5LAojJyBmb3IgZXhhbXBsZSwgaW4gdGhlIGVkZ2Ugb2YgdGhlIGRhdGEuCiMnIAojJyBDb21wYXJlIHRoZSBwb3N0ZXJpb3IgZHJhd3MgdG8gdGhlIG9wdGltaXplZCBwYXJhbWV0ZXJzCm9kcmF3c19ncGNvdmZnIDwtIGFzX2RyYXdzX2RmKG9wdF9ncGNvdmZnJGRyYXdzKCkpCmRyYXdzX2dwY292ZmcgJT4lCiAgdGhpbl9kcmF3cyh0aGluPTUpICU+JQogIGFzX2RyYXdzX2RmKCkgJT4lCiAgZ2dwbG90KGFlcyh4PWxlbmd0aHNjYWxlX2YseT1zaWdtYV9mKSkrCiAgZ2VvbV9wb2ludChjb2xvcj1zZXQxWzJdKSsKICBnZW9tX3BvaW50KGRhdGE9b2RyYXdzX2dwY292ZmcsY29sb3I9c2V0MVsxXSxzaXplPTQpKwogIGFubm90YXRlKCJ0ZXh0Iix4PW1lZGlhbihkcmF3c19ncGNvdmZnJGxlbmd0aHNjYWxlX2YpLAogICAgICAgICAgIHk9bWF4KGRyYXdzX2dwY292Zmckc2lnbWFfZikrMC4xLAogICAgICAgICAgIGxhYmVsPSdQb3N0ZXJpb3IgZHJhd3MnLGhqdXN0PTAuNSxjb2xvcj1zZXQxWzJdLHNpemU9NikrCiAgYW5ub3RhdGUoInRleHQiLHg9b2RyYXdzX2dwY292ZmckbGVuZ3Roc2NhbGVfZiswLjAxLAogICAgICAgICAgIHk9b2RyYXdzX2dwY292Zmckc2lnbWFfZiwKICAgICAgICAgICBsYWJlbD0nT3B0aW1pemVkJyxoanVzdD0wLGNvbG9yPXNldDFbMV0sc2l6ZT02KQoKIycgT3B0aW1pemF0aW9uIHJlc3VsdCBpcyBmYXIgZnJvbSBiZWluZyByZXByZXNlbnRhdGl2ZSBvZiB0aGUKIycgcG9zdGVyaW9yLgojJyAKCiMnICMjIEdQIG1vZGVsIHdpdGggSGlsYmVydCBiYXNpcyBmdW5jdGlvbnMKIycKIycgVGhlIGNvdmFyaWFuY2UgbWF0cml4IGFwcHJvYWNoIHJlcXVpcmVzIGNvbXB1dGF0aW9uIG9mIENob2xlc2t5IG9mCiMnIHRoZSBjb3ZhcmlhbmNlIG1hdHJpeCB3aGljaCBoYXMgdGltZSBjb3N0IE8obl4zKSBhbmQgdGhpcyBpcyBuZWVkcwojJyB0byBiZSBkb25lIGV2ZXJ5IHRpbWUgdGhlIHBhcmFtZXRlcnMgY2hhbmdlLCB3aGljaCBpbiBjYXNlIG9mIE1DTUMKIycgY2FuIGJlIHF1aXRlIG1hbnkgdGltZXMgYW5kIHRodXMgdGhlIGNvbXB1dGF0aW9uIHRpbWUgY2FuIGJlCiMnIHNpZ25pZmljYW50IHdoZW4gbiBncm93cy4gT25lIHdheSB0byBzcGVlZCB1cCB0aGUgY29tcHV0YXRpb24gaW4KIycgbG93IGRpbWVuc2lvbmFsIGNvdmFyaWF0ZSBjYXNlIGlzIHRvIHVzZSBiYXNpcyBmdW5jdGlvbgojJyBhcHByb3hpbWF0aW9uIHdoaWNoIGNoYW5nZXMgdGhlIEdQIHRvIGEgbGluZWFyIG1vZGVsLiBIZXJlIHdlIHVzZQojJyBIaWxiZXJ0IHNwYWNlIGJhc2lzIGZ1bmN0aW9ucy4KIycgCiMnIENvZGUgZm9yIGlsbHVzdHJhdGluZyB0aGUgYmFzaXMgZnVuY3Rpb25zCiMnIE1vZGVsIGNvZGUKZmlsZWJmMCA8LSAiZ3BiZjAuc3RhbiIKd3JpdGVMaW5lcyhyZWFkTGluZXMoZmlsZWJmMCkpCiMnIFRoZSBtb2RlbCBjb2RlIGluY2x1ZGVzIEhpbGJlcnQgc3BhY2UgYmFzaXMgZnVuY3Rpb24gaGVscGVycwp3cml0ZUxpbmVzKHJlYWRMaW5lcygiZ3BiYXNpc2Z1bl9mdW5jdGlvbnMuc3RhbiIpKQoKIycgQ29tcGlsZSBiYXNpcyBmdW5jdGlvbiBnZW5lcmF0aW9uIGNvZGUKbW9kZWxiZjAgPC0gY21kc3Rhbl9tb2RlbChzdGFuX2ZpbGUgPSBmaWxlYmYwLCBpbmNsdWRlX3BhdGhzID0gIi4iKQoKIycgRGF0YSB0byBiZSBwYXNzZWQgdG8gU3RhbgpzdGFuZGF0YWJmMCA8LSBsaXN0KHg9c2VxKDAsMSxsZW5ndGgub3V0PTEwMCksCiAgICAgICAgICAgICAgICAgICAgTj0xMDAsCiAgICAgICAgICAgICAgICAgICAgY19mPTEuNSwgIyBmYWN0b3IgYyBvZiBiYXNpcyBmdW5jdGlvbnMgZm9yIEdQIGZvciBmMQogICAgICAgICAgICAgICAgICAgIE1fZj00MCwgICMgbnVtYmVyIG9mIGJhc2lzIGZ1bmN0aW9ucyBmb3IgR1AgZm9yIGYxCiAgICAgICAgICAgICAgICAgICAgc2lnbWFfZj0xLAogICAgICAgICAgICAgICAgICAgIGxlbmd0aHNjYWxlX2Y9MSkgCiMnIEdlbmVyYXRlIGJhc2lzIGZ1bmN0aW9ucwpmaXhiZjAgPC0gbW9kZWxiZjAkc2FtcGxlKGRhdGE9c3RhbmRhdGFiZjAsIGZpeGVkX3BhcmFtPVRSVUUsCiAgICAgICAgICAgICAgICAgICAgICAgICAgaXRlcj0xLCBpdGVyX3NhbXBsaW5nPTEpCiMnIFRoZXJlIGlzIGNlcnRhaW5seSBlYXNpZXIgd2F5IHRvIGRvIHRoaXMsIGJ1dCB0aGlzIGlzIHdoYXQgSSBjYW1lIHVwIHF1aWNrbHkKcTwtc3Vic2V0KGZpeGJmMCRkcmF3cygpLCB2YXJpYWJsZT0iUEhJX2YiKSAlPiUKICBhc19kcmF3c19tYXRyaXgoKSAlPiUKICBhcy5udW1lcmljKCklPiUKICBtYXRyaXgobnJvdz0xMDAsbmNvbD00MCklPiUKICBhcy5kYXRhLmZyYW1lKCkKaWQgPC0gcm93bmFtZXMocSkKcSA8LSBjYmluZCh4PWFzLm51bWVyaWMoaWQpLCBxKQpxIDwtIHEgJT4lCiAgcGl2b3RfbG9uZ2VyKCF4LAogICAgICAgICAgICAgICBuYW1lc190bz0iaW5kIiwKICAgICAgICAgICAgICAgbmFtZXNfdHJhbnNmb3JtID0gbGlzdChpbmQgPSByZWFkcjo6cGFyc2VfbnVtYmVyKSwKICAgICAgICAgICAgICAgdmFsdWVzX3RvPSJmIiklPiUKICBtdXRhdGUoeD14LzEwMCkKCiMnIFBsb3QgMTAgZmlyc3QgYmFzaXMgZnVuY3Rpb25zCnEgJT4lCiAgZmlsdGVyKGluZDw9MTApICU+JQogIGdncGxvdChhZXMoeD14LCB5PWYsIGdyb3VwPWluZCkpICsKICBnZW9tX2xpbmUoKSArCiAgZmFjZXRfZ3JpZChyb3dzPXZhcnMoaW5kKSkKCiMnIEFuZCBub3cgdGhlIGFjdHVhbCBtb2RlbCB1c2luZyBHUCBiYXNpcyBmdW5jdGlvbnMgZm9yIGYgYW5kIGcKIycgCiMnIE1vZGVsIGNvZGUKZmlsZV9ncGJmZmcgPC0gImdwYmZmZy5zdGFuIgp3cml0ZUxpbmVzKHJlYWRMaW5lcyhmaWxlX2dwYmZmZykpCgojJyBDb21waWxlIFN0YW4gbW9kZWwKbW9kZWxfZ3BiZmZnIDwtIGNtZHN0YW5fbW9kZWwoc3Rhbl9maWxlID0gZmlsZV9ncGJmZmcsIGluY2x1ZGVfcGF0aHMgPSAiLiIpCgojJyBEYXRhIHRvIGJlIHBhc3NlZCB0byBTdGFuCnN0YW5kYXRhX2dwYmZmZyA8LSBsaXN0KHg9bWN5Y2xlJHRpbWVzLAogICAgICAgICAgICAgICAgICAgICAgICB5PW1jeWNsZSRhY2NlbCwKICAgICAgICAgICAgICAgICAgICAgICAgTj1sZW5ndGgobWN5Y2xlJHRpbWVzKSwKICAgICAgICAgICAgICAgICAgICAgICAgY19mPTEuNSwgIyBmYWN0b3IgYyBvZiBiYXNpcyBmdW5jdGlvbnMgZm9yIEdQIGZvciBmMQogICAgICAgICAgICAgICAgICAgICAgICBNX2Y9NDAsICAjIG51bWJlciBvZiBiYXNpcyBmdW5jdGlvbnMgZm9yIEdQIGZvciBmMQogICAgICAgICAgICAgICAgICAgICAgICBjX2c9MS41LCAjIGZhY3RvciBjIG9mIGJhc2lzIGZ1bmN0aW9ucyBmb3IgR1AgZm9yIGczCiAgICAgICAgICAgICAgICAgICAgICAgIE1fZz00MCkgICMgbnVtYmVyIG9mIGJhc2lzIGZ1bmN0aW9ucyBmb3IgR1AgZm9yIGczCgojJyBPcHRpbWl6ZSBhbmQgZmluZCBNQVAgZXN0aW1hdGUKIysgb3B0X2dwYmZmZywgcmVzdWx0cz0naGlkZScKb3B0X2dwYmZmZyA8LSBtb2RlbF9ncGJmZmckb3B0aW1pemUoZGF0YT1zdGFuZGF0YV9ncGJmZmcsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGluaXQ9MC4xLCBhbGdvcml0aG09J2JmZ3MnKQoKIycgQ2hlY2sgd2hldGhlciBwYXJhbWV0ZXJzIGhhdmUgcmVhc29uYWJsZSB2YWx1ZXMKb2RyYXdzX2dwYmZmZyA8LSBhc19kcmF3c19ydmFycyhvcHRfZ3BiZmZnJGRyYXdzKCkpCnN1YnNldChvZHJhd3NfZ3BiZmZnLCB2YXJpYWJsZT1jKCdpbnRlcmNlcHQnLCdzaWdtYV8nLCdsZW5ndGhzY2FsZV8nKSwKICAgICAgIHJlZ2V4PVRSVUUpCgojJyBDb21wYXJlIHRoZSBtb2RlbCB0byB0aGUgZGF0YQptY3ljbGUgJT4lCiAgbXV0YXRlKEVmPW1lYW4ob2RyYXdzX2dwYmZmZyRmKSwKICAgICAgICAgc2lnbWE9bWVhbihvZHJhd3NfZ3BiZmZnJHNpZ21hKSkgJT4lICAKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYpLCBjb2xvcj1zZXQxWzFdKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYtMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShhZXMoeT1FZisyKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikKCgojJyBUaGUgb3B0aW1pemF0aW9uIG92ZXJmaXRzLCBhcyB3ZSBhcmUgbm93IG9wdGltaXppbmcgdGhlIGpvaW50CiMnIHBvc3RlcmlvciBvZiAyIGNvdmFyaWFuY2UgZnVuY3Rpb24gcGFyYW1ldGVycyBhbmQgMiB4IDQwIGJhc2lzCiMnIGZ1bmN0aW9uIGNvLWVmZmljaWVudHMuCiMnIAojJyBTYW1wbGUgdXNpbmcgZHluYW1pYyBITUMKIysgZml0X2dwYmZmZywgcmVzdWx0cz0naGlkZScKZml0X2dwYmZmZyA8LSBtb2RlbF9ncGJmZmckc2FtcGxlKGRhdGE9c3RhbmRhdGFfZ3BiZmZnLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaXRlcl93YXJtdXA9NTAwLCBpdGVyX3NhbXBsaW5nPTUwMCwgcmVmcmVzaD0xMDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjaGFpbnM9NCwgcGFyYWxsZWxfY2hhaW5zPTQsIGFkYXB0X2RlbHRhPTAuOSkKCiMnIENoZWNrIHdoZXRoZXIgcGFyYW1ldGVycyBoYXZlIHJlYXNvbmFibGUgdmFsdWVzCmRyYXdzX2dwYmZmZyA8LSBhc19kcmF3c19ydmFycyhmaXRfZ3BiZmZnJGRyYXdzKCkpCnN1bW1hcmlzZV9kcmF3cyhzdWJzZXQoZHJhd3NfZ3BiZmZnLAogICAgICAgICAgICAgICAgICAgICAgIHZhcmlhYmxlPWMoJ2ludGVyY2VwdCcsJ3NpZ21hXycsJ2xlbmd0aHNjYWxlXycpLAogICAgICAgICAgICAgICAgICAgICAgIHJlZ2V4PVRSVUUpKQoKIycgQ29tcGFyZSB0aGUgbW9kZWwgdG8gdGhlIGRhdGEKbWN5Y2xlICU+JQogIG11dGF0ZShFZj1tZWFuKGRyYXdzX2dwYmZmZyRmKSwKICAgICAgICAgc2lnbWE9bWVhbihkcmF3c19ncGJmZmckc2lnbWEpKSAlPiUgIAogIGdncGxvdChhZXMoeD10aW1lcyx5PWFjY2VsKSkrCiAgZ2VvbV9wb2ludCgpKwogIGxhYnMoeD0iVGltZSAobXMpIiwgeT0iQWNjZWxlcmF0aW9uIChnKSIpKwogIGdlb21fbGluZShhZXMoeT1FZiksIGNvbG9yPXNldDFbMV0pKwogIGdlb21fbGluZShhZXMoeT1FZi0yKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikrCiAgZ2VvbV9saW5lKGFlcyh5PUVmKzIqc2lnbWEpLCBjb2xvcj1zZXQxWzFdLGxpbmV0eXBlPSJkYXNoZWQiKQoKIycgVGhlIE1DTUMgaW50ZWdyYXRpb24gd29ya3Mgd2VsbCBhbmQgdGhlIG1vZGVsIGZpdCBsb29rcyBnb29kLgojJyAKIycgUGxvdCBwb3N0ZXJpb3IgZHJhd3MgYW5kIHBvc3RlcmlvciBtZWFuIG9mIHRoZSBtZWFuIGZ1bmN0aW9uCmRyYXdzX2dwYmZmZyAlPiUKICB0aGluX2RyYXdzKHRoaW49NSkgJT4lCiAgc3ByZWFkX3J2YXJzKGZbaV0pICU+JQogIHVubmVzdF9ydmFycygpICU+JQogIG11dGF0ZSh0aW1lPW1jeWNsZSR0aW1lc1tpXSkgJT4lCiAgZ2dwbG90KGFlcyh4PXRpbWUsIHk9ZiwgZ3JvdXAgPSAuZHJhdykpICsKICBnZW9tX2xpbmUoY29sb3I9c2V0MVsyXSwgYWxwaGEgPSAwLjEpICsKICBnZW9tX3BvaW50KGRhdGE9bWN5Y2xlLCBtYXBwaW5nPWFlcyh4PXRpbWVzLHk9YWNjZWwpLCBpbmhlcml0LmFlcz1GQUxTRSkrCiAgZ2VvbV9saW5lKGRhdGE9bWN5Y2xlLCBtYXBwaW5nPWFlcyh4PXRpbWVzLHk9bWVhbihkcmF3c19ncGJmZmckZikpLAogICAgICAgICAgICBpbmhlcml0LmFlcz1GQUxTRSwgY29sb3I9c2V0MVsxXSwgc2l6ZT0xKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKQoKIycgV2UgY2FuIGFsc28gcGxvdCB0aGUgcG9zdGVyaW9yIGRyYXdzIG9mIHRoZSBsYXRlbnQgZnVuY3Rpb25zLCB3aGljaAojJyBpcyBhIGdvb2QgcmVtaW5kZXIgdGhhdCBpbmRpdmlkdWFsIGRyYXdzIGFyZSBtb3JlIHdpZ2dseSB0aGFuIHRoZQojJyBhdmVyYWdlIG9mIHRoZSBkcmF3cywgYW5kIHRodXMgc2hvdyBiZXR0ZXIgYWxzbyB0aGUgdW5jZXJ0YWludHksCiMnIGZvciBleGFtcGxlLCBpbiB0aGUgZWRnZSBvZiB0aGUgZGF0YS4KIycgCiMnIENvbXBhcmUgdGhlIHBvc3RlcmlvciBkcmF3cyB0byB0aGUgb3B0aW1pemVkIHBhcmFtZXRlcnMKb2RyYXdzX2dwYmZmZyA8LSBhc19kcmF3c19kZihvcHRfZ3BiZmZnJGRyYXdzKCkpCmRyYXdzX2dwYmZmZyAlPiUKICB0aGluX2RyYXdzKHRoaW49NSkgJT4lCiAgYXNfZHJhd3NfZGYoKSAlPiUKICBnZ3Bsb3QoYWVzKHg9bGVuZ3Roc2NhbGVfZix5PXNpZ21hX2YpKSsKICBnZW9tX3BvaW50KGNvbG9yPXNldDFbMl0pKwogIGdlb21fcG9pbnQoZGF0YT1vZHJhd3NfZ3BiZmZnLGNvbG9yPXNldDFbMV0sc2l6ZT00KSsKICBhbm5vdGF0ZSgidGV4dCIseD1tZWRpYW4oZHJhd3NfZ3BiZmZnJGxlbmd0aHNjYWxlX2YpLAogICAgICAgICAgIHk9bWF4KGRyYXdzX2dwYmZmZyRzaWdtYV9mKSswLjEsCiAgICAgICAgICAgbGFiZWw9J1Bvc3RlcmlvciBkcmF3cycsaGp1c3Q9MC41LGNvbG9yPXNldDFbMl0sc2l6ZT02KSsKICBhbm5vdGF0ZSgidGV4dCIseD1vZHJhd3NfZ3BiZmZnJGxlbmd0aHNjYWxlX2YrMC4wMSwKICAgICAgICAgICB5PW9kcmF3c19ncGJmZmckc2lnbWFfZiwKICAgICAgICAgICBsYWJlbD0nT3B0aW1pemVkJyxoanVzdD0wLGNvbG9yPXNldDFbMV0sc2l6ZT02KQoKIycgT3B0aW1pemF0aW9uIHJlc3VsdCBpcyBmYXIgZnJvbSBiZWluZyByZXByZXNlbnRhdGl2ZSBvZiB0aGUKIycgcG9zdGVyaW9yLgojJyAKCiMnICMjIEdQIG1vZGVsIHdpdGggSGlsYmVydCBiYXNpcyBmdW5jdGlvbnMgYW5kIE1hdGVybiBjb3ZhcmlhbmNlCiMnIAojJyBFeHBvbmVudGlhdGVkIHF1YWRyYXRpYyBpcyBzb21ldGltZXMgY29uc2lkZXJlZCB0byBiZSB0b28gc21vb3RoIGFzCiMnIGFsbCB0aGUgZGVyaXZhdGl2ZXMgYXJlIGNvbnRpbnVvcy4gRm9yIGNvbXBhcmlzb24gd2UgdXNlIE1hdGVybgojJyBjb3ZhcmlhbmNlLiBUaGUgSGlsYmVydCBzcGFjZSBiYXNpcyBmdW5jdGlvbnMgYXJlIHRoZSBzYW1lIGFuZCBvbmx5CiMnIHRoZSBzcGVjdHJhbCBkZW5zaXR5IHZhbHVlcyBjaGFuZ2UgKHRoYXQgaXMgZGlmZmVyZW50IGJhc2lzCiMnIGZ1bmN0aW9ucyBoYXZlIGEgZGlmZmVyZW50IHdlaWdodGluZykuCiMnIAojJyBNb2RlbCBjb2RlCmZpbGVfZ3BiZmZnMiA8LSAiZ3BiZmZnX21hdGVybi5zdGFuIgp3cml0ZUxpbmVzKHJlYWRMaW5lcyhmaWxlX2dwYmZmZzIpKQoKIycgQ29tcGlsZSBTdGFuIG1vZGVsCm1vZGVsX2dwYmZmZzIgPC0gY21kc3Rhbl9tb2RlbChzdGFuX2ZpbGUgPSBmaWxlX2dwYmZmZzIsIGluY2x1ZGVfcGF0aHMgPSAiLiIpCgojJyBEYXRhIHRvIGJlIHBhc3NlZCB0byBTdGFuCnN0YW5kYXRhX2dwYmZmZzIgPC0gbGlzdCh4PW1jeWNsZSR0aW1lcywKICAgICAgICAgICAgICAgICAgICAgICAgeT1tY3ljbGUkYWNjZWwsCiAgICAgICAgICAgICAgICAgICAgICAgIE49bGVuZ3RoKG1jeWNsZSR0aW1lcyksCiAgICAgICAgICAgICAgICAgICAgICAgIGNfZj0xLjUsICMgZmFjdG9yIGMgb2YgYmFzaXMgZnVuY3Rpb25zIGZvciBHUCBmb3IgZjEKICAgICAgICAgICAgICAgICAgICAgICAgTV9mPTQwLCAgIyBudW1iZXIgb2YgYmFzaXMgZnVuY3Rpb25zIGZvciBHUCBmb3IgZjEKICAgICAgICAgICAgICAgICAgICAgICAgY19nPTEuNSwgIyBmYWN0b3IgYyBvZiBiYXNpcyBmdW5jdGlvbnMgZm9yIEdQIGZvciBnMwogICAgICAgICAgICAgICAgICAgICAgICBNX2c9NDApICAjIG51bWJlciBvZiBiYXNpcyBmdW5jdGlvbnMgZm9yIEdQIGZvciBnMwoKIycgU2FtcGxlIHVzaW5nIGR5bmFtaWMgSE1DCiMrIGZpdF9ncGJmZmcyLCByZXN1bHRzPSdoaWRlJwpmaXRfZ3BiZmZnMiA8LSBtb2RlbF9ncGJmZmcyJHNhbXBsZShkYXRhPXN0YW5kYXRhX2dwYmZmZzIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpdGVyX3dhcm11cD01MDAsIGl0ZXJfc2FtcGxpbmc9NTAwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY2hhaW5zPTQsIHBhcmFsbGVsX2NoYWlucz00LCBhZGFwdF9kZWx0YT0wLjkpCgojJyBDaGVjayB3aGV0aGVyIHBhcmFtZXRlcnMgaGF2ZSByZWFzb25hYmxlIHZhbHVlcwpkcmF3c19ncGJmZmcyIDwtIGFzX2RyYXdzX3J2YXJzKGZpdF9ncGJmZmcyJGRyYXdzKCkpCnN1bW1hcmlzZV9kcmF3cyhzdWJzZXQoZHJhd3NfZ3BiZmZnMiwKICAgICAgICAgICAgICAgICAgICAgICB2YXJpYWJsZT1jKCdpbnRlcmNlcHQnLCdzaWdtYV8nLCdsZW5ndGhzY2FsZV8nKSwKICAgICAgICAgICAgICAgICAgICAgICByZWdleD1UUlVFKSkKCiMnIENvbXBhcmUgdGhlIG1vZGVsIHRvIHRoZSBkYXRhCm1jeWNsZSAlPiUKICBtdXRhdGUoRWY9bWVhbihkcmF3c19ncGJmZmcyJGYpLAogICAgICAgICBzaWdtYT1tZWFuKGRyYXdzX2dwYmZmZzIkc2lnbWEpKSAlPiUgIAogIGdncGxvdChhZXMoeD10aW1lcyx5PWFjY2VsKSkrCiAgZ2VvbV9wb2ludCgpKwogIGxhYnMoeD0iVGltZSAobXMpIiwgeT0iQWNjZWxlcmF0aW9uIChnKSIpKwogIGdlb21fbGluZShhZXMoeT1FZiksIGNvbG9yPXNldDFbMV0pKwogIGdlb21fbGluZShhZXMoeT1FZi0yKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikrCiAgZ2VvbV9saW5lKGFlcyh5PUVmKzIqc2lnbWEpLCBjb2xvcj1zZXQxWzFdLGxpbmV0eXBlPSJkYXNoZWQiKQoKIycgVGhlIE1DTUMgaW50ZWdyYXRpb24gd29ya3Mgd2VsbCBhbmQgdGhlIG1vZGVsIGZpdCBsb29rcyBnb29kLgojJyAKIycgUGxvdCBwb3N0ZXJpb3IgZHJhd3MgYW5kIHBvc3RlcmlvciBtZWFuIG9mIHRoZSBtZWFuIGZ1bmN0aW9uCmRyYXdzX2dwYmZmZzIgJT4lCiAgdGhpbl9kcmF3cyh0aGluPTUpICU+JQogIHNwcmVhZF9ydmFycyhmW2ldKSAlPiUKICB1bm5lc3RfcnZhcnMoKSAlPiUKICBtdXRhdGUodGltZT1tY3ljbGUkdGltZXNbaV0pICU+JQogIGdncGxvdChhZXMoeD10aW1lLCB5PWYsIGdyb3VwID0gLmRyYXcpKSArCiAgZ2VvbV9saW5lKGNvbG9yPXNldDFbMl0sIGFscGhhID0gMC4xKSArCiAgZ2VvbV9wb2ludChkYXRhPW1jeWNsZSwgbWFwcGluZz1hZXMoeD10aW1lcyx5PWFjY2VsKSwgaW5oZXJpdC5hZXM9RkFMU0UpKwogIGdlb21fbGluZShkYXRhPW1jeWNsZSwgbWFwcGluZz1hZXMoeD10aW1lcyx5PW1lYW4oZHJhd3NfZ3BiZmZnMiRmKSksCiAgICAgICAgICAgIGluaGVyaXQuYWVzPUZBTFNFLCBjb2xvcj1zZXQxWzFdLCBzaXplPTEpKwogIGxhYnMoeD0iVGltZSAobXMpIiwgeT0iQWNjZWxlcmF0aW9uIChnKSIpCgojJyBXZSBzZWUgdGhhdCB3aGVuIHVzaW5nIE1hdGVybiBjb3ZhcmlhbmNlIGluc3RlYWQgb2YgdGhlCiMnIGV4cG9uZW50aWF0ZWQgcXVhZHJhdGljLCB0aGUgbW9kZWwgZml0IGlzIG1vcmUgd2lnZ2dseS4KIycgCg==